Pagini recente » Cod sursa (job #1253193) | Cod sursa (job #1204480) | Cod sursa (job #1838749) | Cod sursa (job #1146291) | Cod sursa (job #1201272)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const int BASE = 91;
const int MOD = 1e9 + 7;
const int Lmax = 2e6 + 2;
char A[Lmax];
char B[Lmax];
int N, M;
vector <int> match;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> ( A + 1 );
in >> ( B + 1 );
N = strlen( A + 1 );
M = strlen( B + 1 );
int hashP = 0;
int rollingHash = 0;
int baseN = 1;
if ( N > M )
{
out << "0\n";
return 0;
}
for ( int i = 1; i <= N; ++i )
{
baseN = ( 1LL * baseN * BASE ) % MOD;
hashP = ( 1LL * hashP * BASE + A[i] ) % MOD;
rollingHash = ( 1LL * rollingHash * BASE + B[i] ) % MOD;
}
if ( hashP == rollingHash )
{
match.push_back( 1 );
}
for ( int i = N + 1; i <= M; ++i )
{
rollingHash = ( ( 1LL * rollingHash * BASE ) % MOD + B[i] - ( 1LL * baseN * B[i - N] ) % MOD + MOD ) % MOD;
if ( hashP == rollingHash )
{
match.push_back( i - N );
}
}
out << match.size() << "\n";
for ( int i = 0; i < min( 1000, (int)match.size() ); ++i )
{
out << match[i] << " ";
}
out << "\n";
return 0;
}