Pagini recente » Cod sursa (job #1614802) | Cod sursa (job #1432285) | Cod sursa (job #829401) | Cod sursa (job #2442415) | Cod sursa (job #501239)
Cod sursa(job #501239)
#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,sir[1001],nr,poww,MOD2,HA2,HB2,poww2;
char A[2000100],B[2000100];
long long HA,HB;
int main () {
fscanf(f,"%s%s",A,B); N = strlen(A); M = strlen(B);
MOD = 100020; MOD2 = 110009;
/*k = -1 ;
for ( i = 0 ; i <= 9 ; ++i )
hash[ i + '0' ] = ++k;
for ( i = 'A' ; i <= 'Z' ; ++i )
hash[i] = ++k;
for ( i = 'a' ; i <= 'z' ; ++i )
hash[i] = ++k;
*/
//baza 64
bz = 257;
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;
if ( i != N - 1 ){
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;
if ( nr < 1000 )
sir[nr] = i - N + 1;
}
}
fprintf(g,"%d\n",nr);
for ( i = 1 ; i <= nr ; ++i )
fprintf(g,"%d ",sir[i]);
fclose(f);
fclose(g);
return 0;
}