Pagini recente » Cod sursa (job #585840) | Cod sursa (job #2274678) | Cod sursa (job #2914717) | Cod sursa (job #2886572) | Cod sursa (job #2572994)
#include <bits/stdc++.h>
#define LGMAX 2000005
#define MOD1 45007
#define MOD2 45013
#define P 80
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
vector < int > R;
char a[LGMAX], b[LGMAX];
int main()
{
int lg_a, lg_b, i, hash1a = 0, hash2a = 0, hash1 = 0, hash2 = 0, P1 = 1, P2 = 1, nr;
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 + a[i] - '0' + 1 ) % MOD1;
hash2a = ( hash2a * P + a[i] - '0' + 1 ) % MOD2;
hash1 = ( hash1 * P + b[i] - '0' + 1 ) % MOD1;
hash2 = ( hash2 * P + b[i] - '0' + 1 ) % MOD2;
if ( i != 0 ) P1 = ( P1 * P ) % MOD1, P2 = ( P2 * P ) % MOD2;
}
if ( hash1a == hash1 && hash2a == hash2 ) R.push_back ( 0 );
for ( i = lg_a ; i < lg_b ; i++ )
{
hash1 = ( ( hash1 - ( P1 * ( b[i-lg_a] - '0' + 1 ) ) % MOD1 + MOD1 ) * P + b[i] - '0' + 1 ) % MOD1;
hash2 = ( ( hash2 - ( P2 * ( b[i-lg_a] - '0' + 1 ) ) % MOD2 + MOD2 ) * P + b[i] - '0' + 1 ) % MOD2;
if ( hash1 == hash1a && hash2 == hash2a ) R.push_back ( i - lg_a + 1 );
}
fout << R.size() << '\n';
nr = R.size();
nr = min ( nr, 1000 );
for ( i = 0 ; i < nr ; i++ ) fout << R[i] << ' ';
return 0;
}