Pagini recente » Cod sursa (job #2211814) | Cod sursa (job #2291940) | Cod sursa (job #2006020) | Cod sursa (job #922883) | Cod sursa (job #1528503)
#include <cstdio>
#define MAXN 2000000
FILE*fi,*fout;
char v1[MAXN+1],v2[MAXN+1],poz[1000],a;
int pi[MAXN+1];
inline int cit(char *v){
int n=0;
a=fgetc(fi);
while(a!='\n'){
v[++n]=a;
a=fgetc(fi);
}
return n;
}
inline void cauta(char *v,int n){
int i,j;
pi[1]=0;
for(i=2;i<=n;i++){
if(v[i]==v[pi[i-1]+1])
pi[i]=pi[i-1]+1;
else{
j=i-1;
while(j>1&&v[pi[j]+1]!=v[i])
j=pi[j];
pi[i]=pi[j];
if(v[i]==v[1]&&pi[i]==0)
pi[i]=1;
}
}
}
int main(){
int n,m,i,kmp,con;
fi=fopen("strmatch.in" ,"r");
fout=fopen("strmatch.out" ,"w");
n=cit(v1);
m=cit(v2);
cauta(v1,n);
kmp=con=0;
for(i=1;i<m;i++){
while(v2[i]!=v1[kmp+1]&&kmp!=0)
kmp=pi[kmp];
if(v2[i]==v1[kmp+1])
kmp++;
if(kmp==n)
if(con<1000)
poz[con++]=i-kmp;
}
fprintf(fout,"%d\n" ,con);
for(i=0;i<con;i++)
fprintf(fout,"%d " ,poz[i]);
fclose(fi);
fclose(fout);
return 0;
}