Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <vector>
- using namespace std;
- string t, p;
- int fail[1000001];
- vector<int>anslist;
- int main()
- {
- getline(cin, t);
- getline(cin, p);
- fail[0] = -1;
- for (int i = 1; i < p.size(); i++)
- {
- int point = i - 1;
- fail[i] = -1;
- while (point != -1) {
- point = fail[point];
- if (p[i] == p[point + 1]) {
- fail[i] = point + 1;
- break;
- }
- }
- }
- int idx = 0;
- for (int i = 0; i < t.size(); i++)
- {
- if (p[idx] == t[i]) idx++;
- else if (idx) {
- idx = fail[idx - 1] + 1;
- if (p[idx] == t[i]) idx++;
- }
- if (idx == p.size()) {
- idx = fail[idx - 1] + 1;
- anslist.push_back(i - p.size());
- }
- }
- cout << anslist.size()<<'\n';
- for (int i = 0; i < anslist.size(); i++)
- cout << anslist[i] + 2 << ' ';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement