Блог

Я хочу принимать входные данные от пользователя определенным образом, например, следующим образом :

 L1 L2 L3 N 
  

L1, L2, L3 — это строки, разделенные пробелами. А N — целое число. Я пытался использовать cin , но это было медленно. Мне нужно быстро получить ввод. Также строка L2 повторяется N раз. Поэтому я должен хранить l1 l2*N l3 . Я пробовал string, но он становится слишком медленным. Я получаю TLE.

Вот как я их сохранил :

  #include<bits/stdc  .h>
using namespace std;
int main (){
 string l1,l2,l3;
  int n;
  cin>>l1>>l2>>l3>>n;
  string r;
 r.reserve(l1.size() n * l2.size() l3.size());
r  = l1;
 for (int i=0; i<n;i  )
  r  =l2;

 r  = l3;
 cout<<r<<endl;
return 0;
 }

And then iterated it in 2 separate for loops with maximum 1000 iterations in each loop.
  

Как я могу эффективно их хранить? Я знаю о векторах, но я в них не силен. Итак, если кто-нибудь знает, как сохранить их в этой последовательности в векторе, пожалуйста, помогите мне. Или, если они могут быть сохранены в массиве символов, то как это сделать?

Хорошо. Итак, давайте начнем с выделения фактического чтения из другого кода:

 struct foo { 
    std::string l1, l2, l3; 
    int n;

    friend std::istream amp;operator>>(std::istream amp;is, foo amp;f) { 
       return is >> f.l1, >> f.l2 >> f.l3 >> n;
    }
};
  

С помощью этого мы можем читать в файле, полном этих записей, в вектор с чем-то вроде этого:

 std::vector<foo> data { std::istream_iterator<foo>(infile), {} };
  

Я бы предположил, что это (само по себе) не будет узким местом. Вероятно, есть более быстрые способы выполнить работу, если это действительно необходимо, но я сомневаюсь, что это действительно необходимо.

Основываясь на комментариях о том, как должен выполняться поиск, мы можем выполнять поиск, даже не расширяя вторую строку до n вхождений l2 .

Поиск выполняется для одного символа от начала строки до последнего (самого правого) появления какого-либо другого символа.

Поскольку этот шаблон «end» представляет собой один символ, мы можем сделать это довольно легко, вообще не расширяя среднюю строку ( L2 ). Логика в основном:

 if L3 contains end_pattern
   total = count(L1)   count(L2) * n   count(L3.substr(0, pattern_pos))
else if L2 contains end_pattern
    total = count(L1)   count(L2) * (n-1)   count(L2.substr(0, pattern_pos))
else if L1 contains end_pattern
    total = count(L1.substr(0, pattern_pos))
else
    total = 0; // pattern isn't present anywhere
  

По крайней мере, как описано в комментариях, похоже, нет необходимости в алгоритме O (N ²), описанном в комментариях.