Pagini recente » Cod sursa (job #2171809) | Cod sursa (job #456826) | Cod sursa (job #2649780) | Cod sursa (job #3175574) | Cod sursa (job #3290127)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
#define cin fin
#define cout fout
const int Nmax = 2e6 + 5;
const int p = 31;
int mod;
vector<int> ans;
long long h[Nmax], powP;
inline void precalc_hashuri( const string &s ) {
int i;
powP = 1;
for( i = 1; i <= s.size(); i ++ ) {
h[i] = ( h[i-1] + powP * ( s[i-1] - 'A' + 1) ) % mod;
powP = ( powP * p ) % mod;
}
}
int main()
{
int i, A;
string a, b;
long long hashA = 0, val;
mod = ( rand() % 50000 ) + Nmax;
cin >> a >> b;
if( a.size() > b.size() ) {
cout << 0 << '\n';
return 0;
}
A = a.size();
precalc_hashuri( b );
powP = 1;
for( i = 0; i < a.size(); i ++ ) {
hashA = ( hashA + (powP * ( a[i] - 'A' + 1)) ) % mod;
powP = ( powP * p ) % mod;
}
powP = 1;
for( i = 0; i < b.size() - A + 1; i ++ ) {
val = ( h[i+A] - h[i] + mod ) % mod;
int x = ((hashA * powP) % mod);
if( ((hashA * powP) % mod) == val )
ans.push_back( i );
powP = ( powP * p ) % mod;
}
cout << ans.size() << '\n';
for( i = 0; i < min( (int) ans.size(), 1000) ; i++ )
cout << ans[i] << " ";
return 0;
}