Pagini recente » Monitorul de evaluare | Cod sursa (job #2716399) | Cod sursa (job #773342) | Cod sursa (job #1573165) | Cod sursa (job #1201885)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const ull BASE = 137;
const int Lmax = 2e6 + 2;
vector <int> match;
char A[Lmax];
char B[Lmax];
int N, M;
ull H[Lmax], Hpow[Lmax];
ull getCodeHash( int i, int dim )
{
return H[i] - H[i + dim] * Hpow[dim];
}
void pregen()
{
Hpow[0] = 1;
for ( int i = 1; i <= M; ++i )
Hpow[i] = Hpow[i - 1] * BASE;
H[M + 1] = 0;
for ( int i = M; i >= 1; i-- )
{
H[i] = H[i + 1] * BASE + B[i];
}
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in.sync_with_stdio( false );
in >> ( A + 1 );
in >> ( B + 1 );
N = strlen( A + 1 );
M = strlen( B + 1 );
if ( N > M )
{
out << "0\n";
return 0;
}
pregen();
ull hash_p = 0;
for ( int i = N; i >= 1; i-- )
{
hash_p = hash_p * BASE + A[i];
}
for ( int i = 1; i <= M - N; ++i )
{
if ( getCodeHash( i, N ) == hash_p )
match.push_back( i - 1 );
}
out << match.size() << "\n";
for ( int i = 0; i < match.size(); ++i )
{
out << match[i] << " ";
}
return 0;
}