fork download
  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
stdin
4
a
b
 
xxx
ababa
dfs
c + +
qwerty
xxxx
stdout
ababa
c + +
xxxx