Pagini recente » Cod sursa (job #2692808) | Cod sursa (job #2713258) | Cod sursa (job #2558867) | Cod sursa (job #2981466) | Cod sursa (job #2713184)
#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[ 1001 ], 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 <= ans; i++ )
fout << index[i] << " ";
}
void init () {
for ( int i = 0; i < 300; i++ ) {
letKey[i] = rand() * rand();
}
}
int main()
{
fin >> a >> b;
init();
RabinKarp();
return 0;
}