Pagini recente » Cod sursa (job #1050834) | Cod sursa (job #1307207) | Cod sursa (job #1580555) | Cod sursa (job #95390) | Cod sursa (job #1203728)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const ull BASE = 666013;
const int Lmax = 2e6 + 2;
vector <int> match;
char A[Lmax];
char B[Lmax];
int N, M;
ull H[Lmax], Hpow[Lmax];
ull getHash( int i, int j )
{
return H[j] - H[i - 1] * Hpow[j - i + 1];
}
void pregen()
{
Hpow[0] = 1;
for ( int i = 1; i <= M; ++i )
Hpow[i] = Hpow[i - 1] * BASE;
for ( int i = 1; i <= M; 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 = 1; i <= N; ++i )
{
hash_p = hash_p * BASE + A[i];
}
for ( int i = 1; i <= M - N; ++i )
{
if ( getHash( i, i + N - 1 ) == hash_p )
match.push_back( i - 1 );
}
out << match.size() << "\n";
for ( int i = 0; i < match.size(); ++i )
{
out << match[i] << " ";
}
return 0;
}