Pagini recente » Cod sursa (job #1514568) | Cod sursa (job #674780) | Cod sursa (job #1691034) | Cod sursa (job #2158832) | Cod sursa (job #1511890)
#include <stdio.h>
#include <cstring>
#define NMAX 2000005
using namespace std;
char A[NMAX];//model
char B[NMAX];//sir
int L[NMAX], N, M, sol[NMAX];
void prefix(){
int k;
L[1] = 0;
for(int p = 2; p <= N; p++){
k = L[p-1];
while(k > 0 && A[k] != A[p-1])
k = L[k];
if(A[k] == A[p-1])
++k;
L[p] = k;
}
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", A, B);
N = strlen(A);//model
M = strlen(B);//sir
prefix();
int k = 0, ind = 0;
for(int t = 1; t <= M; ++t){
while(k > 0 && A[k] != B[t-1])
k = L[k];
if(A[k] == B[t-1])
++k;
if(k == N){
sol[++ind] = t - N;
k = L[k];
}
}
printf("%d\n", ind);
if(ind > 1000)
ind = 1000;
for(int i = 1; i <= ind; ++i)
printf("%d ", sol[i]);
return 0;
}