Cod sursa(job #459799)
#include <string>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#define Alpha 41
#define Beta 71
#define MAlpha 1000033
#define MBeta 1000081
/*
*
*/
using namespace std;
vector< int > r;
string pattern, s;
void RabinKarp( int N, int M )
{
int i, hp, hp2, hs, hs2, pAlpha=1, pBeta=1;
for( hp=hs=hp2=hs2=i=0; i < M; ++i )
{
hp=( hp*Alpha+pattern[i] )%MAlpha;
hp2=( hp2*Beta+pattern[i] )%MBeta;
hs=( hs*Alpha+s[i] )%MAlpha;
hs2=( hs2*Beta+s[i] )%MBeta;
if( i )
pAlpha=(pAlpha*Alpha)%MAlpha, pBeta=(pBeta*Beta)%MBeta;
}
if( hp == hs && hp2 == hs2 )
r.push_back( 0 );
for( ; i < N; ++i )
{
hs=( hs - s[i-M]*pAlpha + MAlpha )%MAlpha;
hs=( hs*Alpha + s[i] )%MAlpha;
hs2=( hs2 - s[i-M]*pBeta + MBeta )%MBeta;
hs2=( hs2*Beta + s[i] )%MBeta;
if( hs == hp && hs2 == hp2 )
r.push_back( i-M+1 );
}
}
int main( void )
{
ifstream in( "strmatch.in" );
getline( in, pattern, '\n' );
getline( in, s );
RabinKarp( s.size(), pattern.size() );
ofstream out( "strmatch.out" );
out<<r.size()<<'\n';
copy( r.begin(), r.begin() + ( 1000 <= r.size() ? 1000 : r.size() ), ostream_iterator< int >( out, " " ) );
out<<'\n';
return EXIT_SUCCESS;
}