Pagini recente » Cod sursa (job #1743087) | Cod sursa (job #2399940) | Cod sursa (job #729201) | Cod sursa (job #1884700) | Cod sursa (job #501257)
Cod sursa(job #501257)
#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){
++nr;
sir[0] = 1;
}
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;
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;
}