Pagini recente » Cod sursa (job #619286) | Cod sursa (job #147413) | Cod sursa (job #1095003) | Cod sursa (job #2830496) | Cod sursa (job #685652)
Cod sursa(job #685652)
#include<stdio.h>
#include<string.h>
#define lim 2000001
FILE * f = fopen("strmatch.in","r");
FILE * g = fopen("strmatch.out","w");
char N[lim],M[lim];
int n,m,k,q,nr,poz[lim],p[lim];
void prefix(){
k=0;
p[1]=0;
for(int i=2;i<=n;i++){
while(k>0 && (N[k+1]!=N[i]) )
k=p[k];
if(N[k+1]==N[i])
k++;
p[i]=k;
}
}
void match(){
q=0;
for(int i=1;i<=m;i++){
while(q>0 && (N[q+1]!=M[i]) )
q=p[q];
if(N[q+1]==M[i])
q++;
if(q==n){
nr++;
poz[i]=i-n;
}
}
}
int main(){
fscanf(f,"%s",&N);
fscanf(f,"/n");
fscanf(f,"%s",&M);
n=strlen(N+1);
m=strlen(M+1);
prefix();
match();
fprintf(g,"%d\n",nr);
int ok=0;
for(int i=1;i<=m&&ok<=1000;i++){
if(poz[i]){
fprintf(g,"%d ",poz[i]);
ok++;
}
}
fclose(f);
fclose(g);
return 0;
}