Pagini recente » Cod sursa (job #2655277) | Cod sursa (job #1306702) | Cod sursa (job #2783421) | Cod sursa (job #2375185) | Cod sursa (job #906605)
Cod sursa(job #906605)
#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=-1;
Next[0] = 0;
for(register int x=1;x<m;++x){
while(k>0 && B[x]!=B[k+1]) k = Next[k];
if(B[x] == B[k+1])
k++;
Next[x] = k;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&B);
scanf("%s",&A);
int k=-1;
n = strlen(A);
m = strlen(B);
prefix();
for(register int i=0;i<n;++i){
while(k>0 && A[i]!=B[k+1]) k = Next[k];
if(A[i] == B[k+1]) k++;
if(k == m-1){
Sol[++nr] = i-m+1;
k = Next[k];
}
}
printf("%d\n",nr);
for(register int i=1;i<=min(nr,1000);++i)
printf("%d ",Sol[i]);
return 0;
}