Pagini recente » Cod sursa (job #2885566) | Cod sursa (job #874740) | Cod sursa (job #1022964) | Cod sursa (job #1734498) | Cod sursa (job #1001038)
#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 = 2;
int baza2 = 5;
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) % mod1;
BN1 = tempBase % mod1;
tempBase =(tempBase* baza1)%mod1;
}
return sum % mod1;
}
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) % mod2;
BN2 = tempBase % mod2;
tempBase = (tempBase*baza2)%mod2;
}
return sum % mod2;
}
void rabinKarp(string a, string b)
{
int sizeA = a.size();
int sizeB = b.size();
int nrOfAparitions=0;
if(sizeA > sizeB) {
fout << 0 << '\n';
return ;
}
int hash1A = hash1(a);
int hash2A = hash2(a);
int hash1B = hash1(b.substr(0,sizeA));
int hash2B = hash2(b.substr(0,sizeA));
for (int i=0; i<=sizeB - sizeA ; i++)
{
if(hash1A == hash1B)
{
if(hash2A == hash2B)
{
aparPos[nrOfAparitions]=i;
nrOfAparitions++;
}
}
hash1B = (hash1B - BN1 * b[i]) % mod1 + mod1;
hash1B = (hash1B * baza1 + b[i + sizeA]) % mod1;
hash2B = (hash2B - (BN2 * b[i])) % mod2 + mod2;
hash2B = (hash2B * baza2 + b[i + sizeA]) % mod2;
}
if(nrOfAparitions < 1000)
fout << nrOfAparitions << '\n';
else
fout << 1000 << '\n';
for(int i=0; i<nrOfAparitions && i < 1000; i++)
{
fout << aparPos[i] << ' ';
}
fout << '\n';
}