Pagini recente » Cod sursa (job #139658) | Cod sursa (job #2491678) | Cod sursa (job #2405123) | Cod sursa (job #710385) | Cod sursa (job #1741394)
#include <cstdio>
#define MAXN 2000000
#define MAXP 1000
char A[MAXN+2],B[MAXN+2];
int pi[MAXN+1];
int rez[MAXP];
int con;
inline void Calc_Prefix(char *A,int n){
int i,k;
pi[1]=0;
k=0;
for(i=2;i<=n;i++){
while(k>0&&A[k+1]!=A[i])
k=pi[k];
if(A[k+1]==A[i])
k++;
pi[i]=k;
}
}
inline void Potrivire(char *A,char *B,int n,int m){
int i,k;
k=0;
for(i=1;i<=m;i++){
while(k>0&&A[k+1]!=B[i])
k=pi[k];
if(A[k+1]==B[i])
k++;
if(k==n){
con++;
if(con<=MAXP)
rez[con]=i-n;
}
}
}
int main(){
FILE*fi,*fout;
int n,i,m;
char a;
fi=fopen("strmatch.in" ,"r");
fout=fopen("strmatch.out" ,"w");
a=fgetc(fi);
n=0;
while(a!='\n'){
A[++n]=a;
a=fgetc(fi);
}
A[n+1]=-1;
a=fgetc(fi);
m=0;
while(a!='\n'){
B[++m]=a;
a=fgetc(fi);
}
Calc_Prefix(A,n);
Potrivire(A,B,n,m);
fprintf(fout,"%d\n" ,con);
for(i=1;i<=con&&i<=MAXP;i++)
fprintf(fout,"%d " ,rez[i]);
fclose(fi);
fclose(fout);
return 0;
}