daily pastebin goal
62%
SHARE
TWEET

pizda

a guest May 17th, 2018 114 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <string>
  5. using namespace std;
  6.  
  7. std::vector<int> pref(string s) {
  8.     int n = s.length();
  9.     std::vector<int> p(n);
  10.     for (int i = 1; i < n; i++) {
  11.         int j = p[i - 1];
  12.         while (j > 0 && s[j] != s[i]) {
  13.             j = p[j - 1];
  14.         }
  15.         p[i] = j;
  16.         if (s[j] == s[i]) {
  17.             p[i]++;
  18.         }
  19.     }
  20.     return p;
  21. }
  22.  
  23. int main() {
  24.     string s, t, f;
  25.     cin >> s;
  26.     cin >> t;
  27.     f = t + '$' + s;
  28.     if (s.length() >= t.length()) {
  29.         f += s.substr(0, t.length() - 1);
  30.     }
  31.     else {
  32.         f += s;
  33.     }
  34.  
  35.     //cout << f;
  36.    
  37.     vector<int> p = pref(f);
  38.     for (int i = t.length()+1; i < f.length(); i++) {
  39.         if (p[i] == t.length()) {
  40.             cout << i - 2*t.length() << " ";
  41.         }
  42.     }
  43.  
  44.     system("pause");
  45. }
RAW Paste Data
Top