Pagini recente » Cod sursa (job #3244753) | Cod sursa (job #3191477) | Cod sursa (job #2557787) | Cod sursa (job #1513470) | Cod sursa (job #2572792)
#include <bits/stdc++.h>
#define LGMAX 200005
#define MOD1 45007
#define MOD2 45013
#define P 60
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int R[LGMAX];
int main()
{
int lg_a, lg_b, i, hash1a = 0, hash2a = 0, hash1 = 0, hash2 = 0, P1 = 1, P2 = 1, nr = 0;
char a[LGMAX], b[LGMAX];
fin.getline ( a, LGMAX );
fin.getline ( b, LGMAX );
lg_a = strlen ( a );
lg_b = strlen ( b );
if ( lg_a > lg_b )
{
fout << 0;
return 0;
}
for ( i = 0 ; i < lg_a ; i++ )
{
hash1a = ( ( ( hash1a * P ) % MOD1 ) + ( a[i] - 'A' + 1 ) ) % MOD1;
hash2a = ( ( ( hash2a * P ) % MOD2 ) + ( a[i] - 'A' + 1 ) ) % MOD2;
hash1 = ( ( ( hash1 * P ) % MOD1 ) + ( b[i] - 'A' + 1 ) ) % MOD1;
hash2 = ( ( ( hash2 * P ) % MOD2 ) + ( b[i] - 'A' + 1 ) ) % MOD2;
if ( i != 0 ) P1 = ( P1 * P ) % MOD1, P2 = ( P2 * P ) % MOD2;
}
if ( hash1a == hash1 && hash2a == hash2 ) R[++nr] = 0;
for ( i = lg_a ; i < lg_b ; i++ )
{
hash1 = ( ( ( hash1 - P1 * ( b[i-lg_a] - 'A' + 1 ) ) * P ) % MOD1 + b[i] - 'A' + 1 ) % MOD1;
hash2 = ( ( ( hash2 - P2 * ( b[i-lg_a] - 'A' + 1 ) ) * P ) % MOD2 + b[i] - 'A' + 1 ) % MOD2;
if ( hash1 == hash1a && hash2 == hash2a ) R[++nr] = i - lg_a + 1;
}
fout << nr << '\n';
nr = min ( nr, 1000 );
for ( i = 1 ; i <= nr ; i++ ) fout << R[i] << ' ';
return 0;
}