Cod sursa(job #1001025)

Utilizator alexx.cosmaCosma Cristian Alexandru alexx.cosma Data 24 septembrie 2013 12:02:29
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#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] << ' ';
    }

}