Pagini recente » Cod sursa (job #1068465) | Cod sursa (job #3263400) | Cod sursa (job #2227660) | Cod sursa (job #2022838) | Cod sursa (job #2868351)
#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];
if(cnt < 1000)
ans[++cnt] = i - m;
}
}
fout << cnt << '\n';
for(int i = 1; i <= cnt; i++)
fout << ans[i] << ' ';
fout << '\n';
return 0;
}