Pagini recente » Cod sursa (job #515643) | Cod sursa (job #1689018) | Cod sursa (job #30084) | Cod sursa (job #234852) | Cod sursa (job #1198637)
#include <cstdio>
FILE*f=fopen("strmatch.in","r");
FILE*h=fopen("strmatch.out","w");
int n,m,pref[2000001],k,rez[2000001],t;
char a[2000001],b[2000001];
int main(){
char c;
fscanf(f,"%c",&c);
while( c!='\n' ){
b[++n]=c;
fscanf(f,"%c",&c);
}
fscanf(f,"%c",&c);
while ( c!='\n' ){
a[++m]=c;
fscanf(f,"%c",&c);
}
pref[1]=0;
for ( int i=2;i<=n;++i ){
k=pref[i-1];
while ( k>0&&b[k+1]!=b[i] )
k=pref[k];
if ( b[k+1]==b[i] )
++k;
pref[i]=k;
}
k=0;
for ( int i=1;i<=m;++i ){
while ( k>0&&b[k+1]!=a[i] )
k=pref[k];
if ( b[k+1]==a[i] )
++k;
if ( k==n ){
rez[++t]=i-n;
k=pref[k];
}
}
fprintf(h,"%d\n",t);
for ( int i=1;i<=t;++i )
fprintf(h,"%d ",rez[i]);
return 0;
}