Pagini recente » Cod sursa (job #1138079) | Cod sursa (job #86738) | Cod sursa (job #2402230) | Cod sursa (job #361197) | Cod sursa (job #2216864)
#include<stdio.h>
#include<string.h>
#define NMAX 2000005
char s[NMAX], p[NMAX];
int answers[NMAX], ans, n, m;
int pi[NMAX];
int main () {
int best = 0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s", p + 1); m = strlen(p + 1);
scanf("%s", s + 1); n = strlen(s + 1);
for(int i = 2; i <= m; i++) {
while(best > 0 && p[best + 1] != p[i]) {
best = pi[best];
}
if(p[best + 1] == p[i])
best++;
pi[i] = best;
}
best = 0;
for(int i = 1; i <= n; i++) {
while(best > 0 && s[i] != p[best + 1])
best = pi[best];
if(s[i] == p[best + 1])
best++;
if(best == m) {
answers[++ans] = i - m + 1;
best = pi[best];
}
}
printf("%d\n", ans);
if(ans > 1000)
ans = 1000;
for(int i = 1; i <= ans; i++)
printf("%d ", answers[i] - 1);
printf("\n");
return 0;
}