Pagini recente » Cod sursa (job #1290169) | Cod sursa (job #1541714) | Monitorul de evaluare | Rating Cuna-Mic Mihai-Cristian (cuna_christian) | Cod sursa (job #1001025)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int aparPos[2000000];
int BN1, BN2;
int baza1 = 33;
int baza2 = 37;
int mod1 = 666013;
int mod2 = 1000007;
void rabinKarp(string a, string b);
int main()
{
string A,B;
fin >> A;
fin >> B;
rabinKarp(A,B);
return 0;
}
int hash1(string a)
{
int sum=0;
int len = a.size();
int tempBase = 1;
for(int i=len-1; i>=0; i--)
{
sum += a[i] * tempBase;
BN1 = tempBase % mod1;
tempBase *= baza1;
}
sum = sum % mod1;
return sum;
}
int hash2(string a)
{
int sum=0;
int len = a.size();
int tempBase = 1;
for(int i=len-1; i>=0; i--)
{
sum += a[i] * tempBase;
BN2 = tempBase % mod2;
tempBase *= baza2;
}
sum = sum % mod2;
return sum;
}
void rabinKarp(string a, string b)
{
int sizeA = a.size();
int sizeB = b.size();
int nrOfAparitions=0;
int hash1A = hash1(a);
int hash2A = hash2(a);
int hash1B = hash1(b.substr(0,sizeA));
int hash2B = hash2(b.substr(0,sizeA));
// we can recompute hashB by simply substracting last index and adding next
for (int i=0; i<sizeB - sizeA ; i++)
{
if(hash1A == hash1B)
{
if(hash2A == hash2B)
{
aparPos[nrOfAparitions]=i;
nrOfAparitions++;
}
}
cout << hash1A << " " << hash2A << " " << hash1B << " " << hash2B << endl;
hash1B = (((hash1B - (BN1 * b[i])%mod1 ))*baza1 + b[i+sizeA] + mod1) %mod1;
hash2B = (((hash2B - (BN2 * b[i])%mod2 ))*baza2 + b[i+sizeA] + mod2) %mod2;
}
fout << nrOfAparitions << '\n';
for(int i=0; i<nrOfAparitions && i < 1000; i++)
{
fout << aparPos[i] << ' ';
}
}