Pagini recente » Cod sursa (job #1851312) | Cod sursa (job #241796) | Cod sursa (job #1776781) | Cod sursa (job #803477) | Cod sursa (job #2713192)
#include <fstream>
#include <string>
#include <cstdlib>
#define LEN_MAX 2000000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string a, b;
typedef unsigned long long U64;
U64 letKey[ 300 ];
int index[ 1010 ], ans;
bool Matching ( int sIndex ) {
for ( int i = 0; i < a.size(); i++ ) {
if ( a[ i ] != b[ sIndex+i ] )
return false;
}
return true;
}
void RabinKarp() {
U64 astrkey = 0;
for ( int i = 0; i < a.size(); i++ )
astrkey ^= letKey[ a[i] ];
U64 key = 0;
for ( int i = 0; i < a.size(); i++ )
key ^= letKey[ b[i] ];
int len = a.size();
for ( int i = len - 1; i < b.size(); i++ ) {
if ( i >= len ) {
key ^= letKey[ b[i-len] ];
key ^= letKey[ b[i] ];
}
if ( key != astrkey )
continue;
if ( Matching( i-len+1 ) ) {
ans++;
if ( ans <= 1000 )
index[ ans ] = i-len+1;
}
}
fout << ans << "\n";
for ( int i = 1; i <= min(ans, 1000); i++ )
fout << index[i] << " ";
}
void init () {
for ( int i = 0; i < 300; i++ ) {
letKey[i] = (U64)rand() * (U64)rand();
}
}
int main()
{
fin >> a >> b;
init();
RabinKarp();
return 0;
}