Pagini recente » Cod sursa (job #1188375) | Painting | time_ | Cod sursa (job #149034) | Cod sursa (job #148431)
Cod sursa(job #148431)
#include <stdio.h>
#include <string.h>
#define nMax 2000005
long n,m,sol,v[nMax];
long urm[nMax];
char A[nMax],B[nMax];
void urmatorul(){
int k=-1,x;
urm[0]=0;
for (x=1;x<m;x++){
while (k>0&&B[k+1]!=B[x])k=urm[k];
if (B[k+1]==B[x])k++;
urm[x]=k;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i,x=-1;
scanf("%s",B);
scanf("%s",A);
n=strlen(A);
m=strlen(B);
urmatorul();
for (i=0;i<n;i++){
while (x>0&&B[x+1]!=A[i])x=urm[x];
if (B[x+1]==A[i])x++;
if (x==m-1){//solutie
x=urm[x];
sol++;
v[sol]=i-m+1;
}
}
printf("%ld\n",sol);
for (i=1;i<=sol;i++)
printf("%ld ",v[i]);
printf("\n");
return 0;
}