Pagini recente » Cod sursa (job #2098612) | Cod sursa (job #1077807) | Cod sursa (job #2768442) | Cod sursa (job #2058553) | Cod sursa (job #963061)
Cod sursa(job #963061)
#include <queue>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#define NMAX 2000003
char A[NMAX], B[NMAX];
int pi[NMAX], sol[10001];
int main(){
int i, k, q, n, m;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
A[0] = B[0] = ' ';
scanf("%s %s", A + 1, B + 1);
n = strlen(A) - 1;
m = strlen(B) - 1;
k = 0;
pi[0] = 0;
for(i = 2; i <= n; i++){
while(k && A[k + 1] != A[i])
k = pi[k];
if (A[k + 1] == A[i])
++k;
pi[i] = k;
}
q = 0;
for(i = 1; i <= m; i++){
while(q && A[q + 1] != B[i])
q = pi[q];
if (A[q + 1] == B[i])
++q;
if (q == n)
sol[++sol[0]] = i - n;
}
printf("%d\n", sol[0]);
for(i = 1; i <= 1000 && i <= sol[0]; i++)
printf("%d ", sol[i]);
return 0;
}