Pagini recente » Cod sursa (job #1021566) | Cod sursa (job #1807766) | Cod sursa (job #1632456) | Istoria paginii utilizator/mario_deaconescu | Cod sursa (job #1821372)
#include <bits/stdc++.h>
FILE *fin, *fout;
///Algoritmul z praduitorilor
#define MAXN 2000000
int n, m;
char N[1+2*MAXN];
int Z[1+2*MAXN];
int st[1+MAXN], last=0;
int main(){
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
char c=fgetc(fin);
while(c!='\n'){
N[++n]=c;
c=fgetc(fin);
}
m=n;
c=fgetc(fin);
while(c!='\n'){
N[++n]=c;
c=fgetc(fin);
}
int L=1, R=1;
for(int k=2;k<=n;k++){
if(k>R){
int i=1, j=k;
while(j<=n && N[i]==N[j]){i++;j++;}
i--;j--;
L=k;R=j;
Z[k]=R-L+1;
}
else{
int k2=k-L+1;
if(Z[k2]<R-k+1)
Z[k]=Z[k2];
else{
int i=R-k+2, j=R+1;
while(j<=n && N[i]==N[j]){i++;j++;}
i--;j--;
L=k;R=j;
Z[k]=j-k+1;
}
}
if(k>m && Z[k]>=m)
st[++last]=k-m-1;
}
fprintf(fout, "%d\n", last);
if(last>1000)
last=1000;
for(int i=1;i<=last;i++)
fprintf(fout, "%d ", st[i]);
fclose(fin);
fclose(fout);
return 0;
}