Pagini recente » Cod sursa (job #3206315) | Cod sursa (job #738314) | Cod sursa (job #1378741) | Cod sursa (job #1660472) | Cod sursa (job #906609)
Cod sursa(job #906609)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMAX 2000001
using namespace std;
int Sol[NMAX];
char A[NMAX],B[NMAX];
int Next[NMAX];
int n,m,nr;
void prefix(){
int k=0;
Next[0] = -1;
for(register int x=1;x<m;++x){
while(k>0 && B[x]!=B[k]) k = Next[k-1];
if(B[x] == B[k])
k++;
Next[x] = k;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&B);
scanf("%s",&A);
int k=0;
n = strlen(A);
m = strlen(B);
prefix();
for(register int i=0;i<n;++i){
while(k>0 && A[i]!=B[k]) k = Next[k-1];
if(A[i] == B[k]) k++;
if(k == m){
Sol[++nr] = i-m+1;
k = Next[k-1];
}
}
printf("%d\n",nr);
for(register int i=1;i<=min(nr,1000);++i)
printf("%d ",Sol[i]);
return 0;
}