Pagini recente » Cod sursa (job #734124) | Cod sursa (job #1902178) | Cod sursa (job #1685634) | Cod sursa (job #3168503) | Cod sursa (job #2868353)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = 2e6 + 5;
string text, pattern;
int pi[MAXN], ans[MAXN], cnt;
int main() {
fin >> pattern >> text;
int n = (int) text.length();
int m = (int) pattern.length();
text = '$' + text;
pattern = '$' + pattern;
for(int i = 2, q = 0; i <= m; i++) {
while(q && pattern[q + 1] != pattern[i])
q = pi[q];
if(pattern[q + 1] == pattern[i])
q++;
pi[i] = q;
}
for(int i = 1, q = 0; i <= n; i++) {
while(q && pattern[q + 1] != text[i])
q = pi[q];
if(pattern[q + 1] == text[i])
q++;
if(q == m) {
q = pi[q];
cnt++;
if(cnt <= 1000)
ans[cnt] = i - m;
}
}
fout << cnt << '\n';
for(int i = 1; i <= min(cnt, 1000); i++)
fout << ans[i] << ' ';
fout << '\n';
return 0;
}