Pagini recente » Cod sursa (job #1500849) | Cod sursa (job #3030769) | Cod sursa (job #1134563) | Cod sursa (job #1338746) | Cod sursa (job #2796569)
#include <stdio.h>
#include <string.h>
#define LUNGMAXX 2000000
#define BAZAHASH 256
#define MOD1 666031
#define MOD2 1000007
#define POZMAXX 1000
using namespace std;
char sirA[LUNGMAXX + 1], sirB[LUNGMAXX + 1];
int poz[POZMAXX], lungA, lungB;
int main() {
FILE *fin, *fout;
int i, pHash1, pHash2, hash1, hash2, pow1, pow2, cnt;
fin = fopen( "strmatch.in", "r" );
fout = fopen( "strmatch.out", "w" );
fgets( sirB, sizeof( sirB ), fin );
lungB = strlen( sirB );
if ( sirB[lungB - 1] == '\n' )
sirB[--lungB] = 0;
fgets( sirA, sizeof( sirA ), fin );
lungA = strlen( sirA );
if ( sirA[lungA - 1] == '\n' )
sirA[--lungA] = 0;
pHash1 = pHash2 = hash1 = hash2 = 0;
pow1 = pow2 = 1;
for ( i = 0; i < lungB; i++ ) {
pHash1 = ( pHash1 * BAZAHASH + sirB[i] ) % MOD1;
pHash2 = ( pHash2 * BAZAHASH + sirB[i] ) % MOD2;
hash1 = ( hash1 * BAZAHASH + sirA[i] ) % MOD1;
hash2 = ( hash2 * BAZAHASH + sirA[i] ) % MOD2;
if ( i > 0 ) {
pow1 = ( pow1 * BAZAHASH ) % MOD1;
pow2 = ( pow2 * BAZAHASH ) % MOD2;
}
}
cnt = 0;
i = lungB;
while ( i <= lungA ) {
if ( hash2 == pHash2 && hash1 == pHash1 ) {
if ( cnt < POZMAXX )
poz[cnt] = i - lungB;
cnt++;
}
hash1 -= sirA[i - lungB] * pow1 % MOD1;
if ( hash1 < 0 )
hash1 += MOD1;
hash2 -= sirA[i - lungB] * pow2 % MOD2;
if ( hash2 < 0 )
hash2 += MOD2;
hash1 = ( hash1 * BAZAHASH + sirA[i] ) % MOD1;
hash2 = ( hash2 * BAZAHASH + sirA[i] ) % MOD2;
i++;
}
fprintf( fout, "%d\n", cnt );
for ( i = 0; i < cnt && i < POZMAXX; i++ ) {
fprintf( fout, "%d ", poz[i] );
}
fclose( fin );
fclose( fout );
return 0;
}