fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define in_range(x,y,z) for (int x=y; x<z; x++)
  5. typedef long long ll;
  6.  
  7. int find_subctr(string t, string s)
  8. {
  9.   const int p = 97;  // основание системы счисления для хеширования строк
  10.   // вычисляем степени числа P, чтобы ускорить процесс хеширования
  11.   vector<ll> p_pow (s.length());
  12.   p_pow[0] = 1;
  13.   for (size_t i=1; i<p_pow.size(); ++i)
  14.     p_pow[i] = p_pow[i-1] * p;
  15.   // вычисляем хеши всех префиксов строки S
  16.   vector<ll> h (s.length());
  17.   for (size_t i=0; i<s.length(); ++i)
  18.     {
  19.       h[i] = (s[i] - 't' + 1) * p_pow[i];
  20.       if (i)  h[i] += h[i-1];
  21.     }
  22.   // посчитаем хеш строки Т
  23.   ll h_t = 0;
  24.   for (size_t i=0; i<t.length(); ++i)
  25.     h_t += (t[i] - 't' + 1) * p_pow[i];
  26.   // сравниваем хеши строки T и подстрок S длины |T|
  27.   for (size_t i = 0; i + t.length() - 1 < s.length(); ++i)
  28.     {
  29.       ll cur_h = h[i+t.length()-1];
  30.       if (i)  cur_h -= h[i-1];
  31.       // если равенство выполняется хотя бы один раз, мы прекращаем поиск
  32.       if (cur_h == h_t * p_pow[i])
  33.         return int(i);
  34.     }
  35.   return -1;
  36. }
  37.  
  38. int main()
  39. {
  40.   vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C
  41.   int n;
  42.   cin >> n;
  43.   string tmp;
  44.   getline(cin,tmp);
  45.   in_range(i,0,n)
  46.     {
  47.       getline(cin,tmp);
  48.       if(tmp.length()==1) C.push_back(tmp);
  49.       T.push_back(tmp);
  50.     }
  51.   while(getline(cin,tmp))
  52.     {
  53.       S.push_back(tmp);
  54.     }
  55.   in_range(i,0,S.size())
  56.     {
  57.       string s=S[i];
  58.       if(s=="") continue; // отсекаем случай пустой строки
  59.       if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором
  60.         {
  61.           in_range(j,0,C.size())
  62.           {
  63.             string c=C[j];
  64.             if(s==c)
  65.               {
  66.                 cout << s << "\n";
  67.                 break;
  68.               }
  69.           }
  70.           continue;
  71.         }
  72.       in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа
  73.       {
  74.         string t=T[j];
  75.         int pos = find_subctr(t,s);
  76.         if(pos>=0)
  77.           {
  78.             cout << s << "\n";
  79.             break;
  80.           }
  81.       }
  82.     }
  83.   return 0;
  84. }
  85.  
  86.  
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
4
a
b
 
xxx
ababa
dfs
c + +
qwerty
xxxx
stdout
copy 
ababa
c + +
xxxx
https://ideone.com/laxq1w
поиск набора образцов
language:
C++14 (clang 8.0)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!