Pagini recente » Cod sursa (job #895962) | Cod sursa (job #1899337) | Cod sursa (job #618464) | Cod sursa (job #501185) | Cod sursa (job #412536)
Cod sursa(job #412536)
#include<stdio.h>
#include<string.h>
FILE *f,*g;
long n,m,i,j,d,ok,prefix[2000500],v[2000500],nr,stop; char model[2000500],sursa[2000500];
int main()
{ f=fopen("strmatch.in","r"); g=fopen("strmatch.out","w");
fscanf(f,"%s",&model); fscanf(f,"%s",&sursa); m=strlen(model)-1; n=strlen(sursa)-1;
if(model[0]==model[1]) prefix[1]=-1; prefix[2]=-1; if(model[0]==model[1]&&model[1]!=model[2]) prefix[2]=1; if(model[0]!=model[1]&&model[1]!=model[2]) prefix[2]=0; prefix[0]=-1;
for(i=2;i<=m;i++)
{ d=i+1; if(d%2==0) d=d/2; else d=d/2+1; j=0; ok=1; if(model[0]==model[i+1]) prefix[i+1]=-1;
while(j<=d&&ok)
{ if(model[j]==model[i-j])
{ if(model[j+1]!=model[i+1]) prefix[i+1]=j+1;
j++;
}
else ok=0;
}
}
i=0; prefix[m+1]=-1; nr=0; stop=1;
while(i<=n-m+1&&stop)
{ j=i;
while(sursa[j]==model[j-i]&&j-i<=m) j++;
if(j-i==m+1)
{ nr++; if(nr<=1000) v[nr]=i; else stop=0;
i++;
}
else i=j-prefix[j-i];
}
fprintf(g,"%ld\n",nr); for(i=1;i<=nr;i++) fprintf(g,"%ld ",v[i]);
fclose(g);
return 0;
}