Pagini recente » Cod sursa (job #2296813) | Cod sursa (job #3038306) | Cod sursa (job #3249128) | Cod sursa (job #2524771) | Cod sursa (job #896916)
Cod sursa(job #896916)
#include<stdio.h>
#include<cstring>
#define maxdim 2000005
#define lim 1000
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
int n,m;
int pi[maxdim],sol[lim+5];
char A[maxdim],B[maxdim];
int main () {
fscanf(f,"%s %s",A+1,B+1);
n = strlen(A+1),m = strlen(B+1);
int k = 0;
for ( int i = 2 ; i <= n ; ++i ){
while ( k > 0 && A[i] != A[k+1] ){
k = pi[k];
}
if ( A[i] == A[k+1] ){
++k;
}
pi[i] = k;
}
k = 0;
for ( int i = 1 ; i <= m ; ++i ){
while ( k > 0 && B[i] != A[k+1] ){
k = pi[k];
}
if ( B[i] == A[k+1] ){
++k;
}
if ( k == n ){
++sol[0];
if ( sol[0] <= lim ) sol[sol[0]] = i-n;
}
}
fprintf(g,"%d\n",sol[0]);
if ( sol[0] > lim ) sol[0] = lim;
for ( int i = 1 ; i <= sol[0] ; ++i ){
fprintf(g,"%d ",sol[i]);
}
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}