Pagini recente » Cod sursa (job #1766474) | Rating Vlad Olteanu (UberMegaLodon) | Cod sursa (job #943564) | Rating faranume (Teodora11) | Cod sursa (job #1001044)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int aparPos[2000000];
int BN1 = 1, BN2 = 1;
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();
BN1 = 1;
for(int i=0; i< len; ++i)
{
sum = (sum * baza1 + a[i]) % mod1;
if(i){
BN1 = (BN1 * baza1) % mod1;
}
}
return sum;
}
int hash2(string a)
{
int sum=0;
int len = a.size();
BN2 = 1;
for(int i=0; i< len; ++i)
{
sum = (sum * baza2 + a[i]) % mod2;
if(i){
BN2 = (BN2 * baza2) % mod2;
}
}
return sum;
}
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);
string c;
for(int i = 0; i < sizeA; ++i) {
c+=b[i];
}
int hash1B = hash1(c);
int hash2B = hash2(c);
b.push_back('0');
for (int i=0; i<=sizeB - sizeA ; i++)
{
if(hash1A == hash1B)
{
if(hash2A == hash2B)
{
if(nrOfAparitions < 1000) {
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;
}
fout << nrOfAparitions << '\n';
for(int i=0; i<nrOfAparitions; i++)
{
fout << aparPos[i] << ' ';
}
fout << '\n';
}