Pagini recente » Cod sursa (job #143001) | Cod sursa (job #334523) | Cod sursa (job #2599650) | Cod sursa (job #2771293) | Cod sursa (job #501249)
Cod sursa(job #501249)
#include<stdio.h>
#include<string>
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
int N,M,hash[257],i,k,MOD,bz,nr,poww,MOD2,HA2,HB2,poww2;
char A[2000100],B[2000100],sir[2000100];
long long HA,HB;
int main () {
fscanf(f,"%s%s",A,B); N = strlen(A); M = strlen(B);
MOD = 100007; MOD2 = 100021;
bz = 73;
poww = poww2 = 1;
for ( i = 0 ; i < N ; ++i ){
HA = ( HA * bz + A[i] ) % MOD;
HB = ( HB * bz + B[i] ) % MOD;
HA2 = ( HA2 * bz + A[i] ) % MOD2;
HB2 = ( HB2 * bz + B[i] ) % MOD2;
}
for ( i = 0 ; i < N - 1 ; ++i ){
poww = ( poww * bz ) % MOD;
poww2 = ( poww2 * bz ) % MOD2;
}
if ( N > M ){
fprintf(g,"0\n");
return 0;
}
if ( HA == HB && HA2 == HB2){
sir[++nr] = 0;
}
for ( i = N ; i < M ; ++i ){
HB = ((HB - (B[i - N] * poww) % MOD + MOD) * bz + B[i] ) % MOD;
HB2 = ((HB2 - (B[i - N] * poww2) % MOD2 + MOD2) * bz + B[i]) % MOD2;
/*
HB -= ( hash[B[i-N]] * poww) % MOD ;
HB = ( HB * bz + hash[B[i]] ) ;
if ( HB > MOD )
HB -= MOD;
HB2 -= ( hash[B[i-N]] * poww2) % MOD2 ;
HB2 = ( HB2 * bz + hash[B[i]] ) ;
if ( HB2 > MOD2 )
HB2 -= MOD2;
*/
if ( HA == HB && HA2 == HB2){
++nr;
sir[ i - N + 1] = 1;
}
}
fprintf(g,"%d\n",nr); nr = 0;
for ( i = 0 ; i < M && nr < 1000 ; ++i ){
if ( sir[i] ){
fprintf(g,"%d ",i);
++nr;
}
}
fclose(f);
fclose(g);
return 0;
}