Pagini recente » Cod sursa (job #1833029) | Cod sursa (job #2679352) | Cod sursa (job #2877496) | Cod sursa (job #2248728) | Cod sursa (job #934475)
Cod sursa(job #934475)
#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,first;
int nrsol,sol[lim+5],Z[maxdim];
char A[maxdim<<1];
int main () {
fscanf(f,"%s",A+1); n = strlen(A+1); first = n;
A[n+1] = '#';
fscanf(f,"%s",A+n+2);
n = strlen(A+1);
int L = 0,R = 0;
for ( int i = 2 ; i <= n ; ++i ){
if ( i > R ){
for ( L = i , R = i-1 ; A[R+1] == A[R-L+2] ; ++R );
Z[i] = R-L+1;
}
else{
int k = i-L+1;
if ( Z[k] < R-i+1 ){
Z[i] = Z[k];
}
else{
for ( L = i ; A[R+1] == A[R-L+2] ; ++R );
Z[i] = R-L+1;
}
}
if ( Z[i] == first ){
++nrsol;
if ( nrsol <= lim ) sol[nrsol] = i-first-2;
}
}
fprintf(g,"%d\n",nrsol);
for ( int i = 1 ; i <= nrsol && i <= lim ; ++i ){
fprintf(g,"%d ",sol[i]);
}
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}