Pagini recente » Cod sursa (job #601765) | Cod sursa (job #2800773) | Cod sursa (job #1798303) | Cod sursa (job #1106921) | Cod sursa (job #1159035)
#include<cstdio>
#include<cstring>
int n,m,i,j,nr,v[2100000],p[2100000],q;
char b[2100000],a[2100000];
FILE *f,*g;
int main(){
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fgets(b+1,2100000,f);
// fscanf(f,"\n");
fgets(a+1,2100000,f);
m=strlen(b+1);
n=strlen(a+1);
m--;
n--;
p[1]=0;
for(i=2;i<=m;i++){
q=p[i];
while(b[i]!=b[q+1]&&q!=0){
q=p[q];
}
if(b[i]==b[q+1])
p[i]=q+1;
else
p[i]=0;
}
q=0;
for(i=1;i<=n;i++){
while(a[i]!=b[q+1]&&q!=0){
q=p[q];
}
if(a[i]==b[q+1])
q++;
if(q==m){
q=p[q];
v[++nr]=i-m;
}
}
fprintf(g,"%d\n",nr);
if(n>1000)
n=1000;
for(i=1;i<=nr;i++){
fprintf(g,"%d ",v[i]);
}
fclose(f);
fclose(g);
return 0;
}