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