Advertisement
noobWD

Untitled

May 20th, 2024
402
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string>
  5. #include <vector>
  6.  
  7.  
  8. using namespace std;
  9.  
  10. string t, p;
  11. int fail[1000001];
  12. vector<int>anslist;
  13.  
  14.  
  15. int main()
  16. {
  17.     getline(cin, t);
  18.     getline(cin, p);
  19.     fail[0] = -1;
  20.     for (int i = 1; i < p.size(); i++)
  21.     {
  22.         int point = i - 1;
  23.         fail[i] = -1;
  24.         while (point != -1) {
  25.             point = fail[point];
  26.             if (p[i] == p[point + 1]) {
  27.                 fail[i] = point + 1;
  28.                 break;
  29.             }
  30.         }
  31.     }
  32.     int idx = 0;
  33.     for (int i = 0; i < t.size(); i++)
  34.     {
  35.         if (p[idx] == t[i]) idx++;
  36.         else if (idx) {
  37.             idx = fail[idx - 1] + 1;
  38.             if (p[idx] == t[i]) idx++;
  39.         }
  40.         if (idx == p.size()) {
  41.             idx = fail[idx - 1] + 1;
  42.             anslist.push_back(i - p.size());
  43.         }
  44.     }
  45.  
  46.     cout << anslist.size()<<'\n';
  47.     for (int i = 0; i < anslist.size(); i++)
  48.         cout << anslist[i] + 2 << ' ';
  49.  
  50.  
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement