Pagini recente » Cod sursa (job #248610) | Cod sursa (job #1242862) | Cod sursa (job #3173300) | Cod sursa (job #423470) | Cod sursa (job #2570094)
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
const int NMAX = (int)2e6;
int pi[NMAX], ans[1000];
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string pattern, text;
getline(cin, pattern);
getline(cin, text);
pi[0] = 0;
int n = pattern.size();
for (int i = 1; i < n; ++i) {
int k = pi[i - 1];
while (k > 0 && pattern[k] != pattern[i])
k = pi[k - 1];
if (pattern[k] == pattern[i])
++k;
pi[i] = k;
}
int m = text.size();
int k = 0, res = 0;
for (int i = 0; i < m; ++i) {
while (k > 0 && pattern[k] != text[i])
k = pi[k - 1];
if (pattern[k] == text[i])
++k;
if (k == n) {
if (res < 1000) ans[res] = i - n + 1;
++res;
}
}
cout << res << endl;
for (int i = 0; i < res; ++i)
cout << ans[i] << ' ';
cout << endl;
}