Pagini recente » Cod sursa (job #1710308) | Cod sursa (job #1486318) | Cod sursa (job #302319) | Cod sursa (job #2851741) | Cod sursa (job #2795759)
#include <stdio.h>
#include <string.h>
using namespace std;
#define BASE 256
#define MOD1 666031
#define MOD2 1000007
const int MAXLEN = 2e6;
char pattern[MAXLEN+1], str[MAXLEN+1];
int poz[1001];
int main() {
FILE *fin, *fout;
int lenp, lenstr, hash1, hash2, Hash1, Hash2, nrap, put1, put2, i;
fin = fopen( "strmatch.in", "r" );
fgets( pattern, sizeof(pattern), fin );
lenp = strlen(pattern);
fgets( str, sizeof(str), fin );
lenstr = strlen(str);
lenp--;
lenstr--;
pattern[lenp] = str[lenstr] = 0;
fclose( fin );
hash1 = hash2 = 0;
Hash1 = Hash2 = 0;
put1 = put2 = 1;
for ( i = 0; i < lenp; i++ ) {
hash1 = ( hash1 * BASE + pattern[i] ) % MOD1;
if( i < lenp - 1 )
hash2 = ( hash2 * BASE + str[i] ) % MOD1;
Hash1 = ( Hash1 * BASE + pattern[i] ) % MOD2;
if( i < lenp - 1 )
Hash2 = ( Hash2 * BASE + str[i] ) % MOD2;
if( i < lenp - 1 ) {
put1 = ( put1 * BASE ) % MOD1;
put2 = ( put2 * BASE ) % MOD2;
}
}
nrap = 0;
for( i = lenp - 1; i < lenstr; i++ ) {
hash2 = ( hash2 * BASE + str[i] ) % MOD1;
Hash2 = ( Hash2 * BASE + str[i] ) % MOD2;
if( hash1 == hash2 && Hash1 == Hash2 ) {
nrap++;
if( nrap <= 1000 )
poz[nrap-1] = i + 1 - lenp;
}
hash2 = ( hash2 - put1 * str[i-lenp+1] ) % MOD1;
Hash2 = ( Hash2 - put2 * str[i-lenp+1] ) % MOD2;
if( hash2 < 0 )
hash2 += MOD1;
if( Hash2 < 0 )
Hash2 += MOD2;
}
fout = fopen( "strmatch.out", "w" );
fprintf( fout, "%d\n", nrap );
i = 0;
while( poz[i] ) {
fprintf( fout, "%d ", poz[i] );
i++;
}
fclose( fout );
return 0;
}