Pagini recente » Cod sursa (job #475420) | Cod sursa (job #211773) | Borderou de evaluare (job #2173669) | Cod sursa (job #679222) | Cod sursa (job #1516290)
#include <cstdio>
#define MAXN 2000000
char v[2*MAXN+1];
int z[2*MAXN+1];
int main(){
FILE*fi,*fout;
int n,con,j,i,l,r,nr;
fi=fopen("strmatch.in" ,"r");
fout=fopen("strmatch.out" ,"w");
n=0;
while(v[n]!='\n')
v[++n]=fgetc(fi);
n--;
nr=n;
while(v[n]!='\n')
v[++n]=fgetc(fi);
l=r=0;
z[1]=n;
for(i=2;i<=n-nr;i++)
if(r<i){
j=i;
while(j<n&&v[j]==v[j-i+1])
j++;
if(r<j-1&&j-1>=i){
l=i;
r=j-1;
}
z[i]=j-i;
}
else
if(z[i-l+1]<r-i+1)
z[i]=z[i-l+1];
else{
j=r+1;
while(j<n&&v[j]==v[j-i+1])
j++;
r=j-1;
l=i;
z[i]=j-i;
}
con=0;
for(i=nr+1;i<n;i++)
if(z[i]>=nr)
con++;
fprintf(fout,"%d\n" ,con);
if(con>1000)
con=1000;
i=nr+1;
while(con){
if(z[i]>=nr){
fprintf(fout,"%d " ,i-nr-1);
con--;
}
i++;
}
fclose(fi);
fclose(fout);
return 0;
}