Pagini recente » Cod sursa (job #774053) | Cod sursa (job #2903324) | Cod sursa (job #995327) | Cod sursa (job #516870) | Cod sursa (job #683330)
Cod sursa(job #683330)
#include<stdio.h>
#include<cstring>
#define maxdim 2000005
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
int n,m,matches;
int pi[maxdim],sol[1005];
char A[maxdim],B[maxdim];
inline void prefix () {
n = strlen(A+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 = k + 1;
}
pi[i] = k;
}
}
inline void kmp (){
m = strlen(B+1);
int q = 0;
for ( int i = 1 ; i <= m ; ++i ){
while ( q > 0 && B[i] != A[q+1] ){
q = pi[q];
}
if ( B[i] == A[q+1] ){
q = q + 1;
}
if ( q == n ){
++matches;
if ( matches <= 1000 ){
sol[matches] = i - n;
}
}
}
}
int main () {
fscanf(f,"%s\n%s",A+1,B+1);
prefix();
kmp();
fprintf(g,"%d\n",matches);
matches = matches <= 1000 ? matches : 1000;
for ( int i = 1 ; i <= matches ; ++i ){
fprintf(g,"%d ",sol[i]);
}
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}