Pagini recente » Cod sursa (job #2038945) | Cod sursa (job #145783) | Cod sursa (job #2159984) | Cod sursa (job #758518) | Cod sursa (job #1543263)
#include <cstdio>
#define maxl 2000005
#include <cstring>
using namespace std;
char M[maxl],N[maxl];
int n,m,prefix[maxl],pos[maxl],res=0;
void Lesen(){
M[0]=N[0]=' ';
scanf("%s",N+1);n=strlen(N);
scanf("%s",M+1);m=strlen(M);
}
void Prafix(){
int k=0;
for(int i=2;i<n;i++){
while(k && N[k+1]!=N[i])k=prefix[k];
if(N[k+1]==N[i])k++;
prefix[i]=k;
}
}
void KMP(){
int k=0;
for(int i=1;i<m;i++){
while(k && N[k+1]!=M[i])k=prefix[k];
if(M[i]==N[k+1])k++;
if(k==n-1){
res++;
if(res<=1000)pos[res]=i-n+1;
}
}
}
void Schreiben(){
printf("%d\n",res);
if(res>1000)res=1000;
for(int i=1;i<=res;++i)printf("%d ",pos[i]);
printf("\n");
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
Lesen();
Prafix();
KMP();
Schreiben();
return 0;
}