Cod sursa(job #1834194)

Utilizator raulmuresanRaul Muresan raulmuresan Data 24 decembrie 2016 01:42:44
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
//Algoritmul lui Rabin Karp
#include<fstream>
#include<vector>
#include<string>
#define P 73
#define MOD1 666013

using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

string a, sir, b;
unsigned i, n, m, k, j,aux,st,dr,x,y,t,poz,p1,p2,hash1,hash2,initHash1 , initHash2,contor,sol ;
vector <unsigned>  myHash[MOD1];

void adauga(unsigned value1)
{
    unsigned hashKey = value1 % MOD1, i;
    myHash[hashKey].push_back(value1);
}

int cauta(unsigned value1)
{
    unsigned gasit = 0, hashKey = value1 % MOD1;
    int i;
    for(i = 0; i < myHash[hashKey].size(); i++)
    {
        if(myHash[hashKey][i] == value1)
        {
            return 1;
        }
    }
    return 0;
}

void cauta(string w)
{
    //fout <<a<<"\n";
    hash1 =  0;
    unsigned trei = 1;
    for(i = 0; i < m ; i++)
    {
        hash1 = hash1 + trei * (w[i] - 'a');
        trei = trei * 3;
        //hash2 = (hash2 * P + w[i]) % MOD2;
    }
    //fout<<hash1<<"\n";
    adauga(hash1);

}


int main()
{
    sol = 0;
    fin >> a >> b;
    n = a.length();
    m = b.length();
    p1 = p2 = 1;
    for(i = 0; i < m - 1; i++)
    {
        p1 = (p1 * 3) % MOD1;
    }




    cauta(b);

    while(fin >> sir)
    {
        //fout << sir<<"\n";
        cauta(sir);
    }
    hash1 = 0;
    unsigned trei = 1;
    for(i = 0; i < m ; i++)
    {
        //fout<<i<<"\n";
        hash1 = hash1 + (a[i] - 'a') * trei;
        trei = trei * 3;
        //hash2 = (hash2 * P + a[i]) % MOD2;
    }
    //fout<<hash1<<"\n";
    sol += cauta(hash1);
    for(i = m ; i < n; i++)
    {
        hash1 = hash1 / 3;
        hash1 = hash1 + (a[i] - 'a') * p1;
        //fout<<hash1<<"\n";
        //hash2 = ((hash2 - ((a[i - m] * p2) % MOD2) + MOD2 ) * P + a[i]) % MOD2;
        sol += cauta(hash1);
        //fout <<hash1<<" "<<hash2<<"\n";
    }


    fout << sol <<"\n";
    //m = b.length();
    //fout<<a<<" "<<b<<"\n";
    /*p1 = p2 = 1;
    initHash1 = initHash2 = 0;
    //calculam functiile hash pentru sirul initial
    for(i = 0; i < n; i++)
    {
        initHash1 = (initHash1 * P + a[i]) % MOD1;
        initHash2 = (initHash2 * P + a[i]) % MOD2;
    }
    for(i = 0; i < n - 1; i++)
    {
        p1 = (p1 * P) % MOD1;
        p2 = (p2 * P) % MOD2;
    }

    if(hash1 == initHash1 && hash2 == initHash2)
    {
        sol.push_back(0);
    }
    //eliminam elementul de pe pozitia i - n
    for(i = n ; i < m; i++)
    {
        hash1 = ((hash1 - ((b[i - n] * p1) % MOD1) + MOD1 ) * P + b[i]) % MOD1;
        hash2 = ((hash2 - ((b[i - n] * p2) % MOD2) + MOD2 ) * P + b[i]) % MOD2;
        if(hash1 == initHash1 && hash2 == initHash2)
        {
            sol.push_back(i - n + 1);
        }
    }

    if(sol.size() > 1000 ) contor = 1000;
    else contor = sol.size();



    fout << sol.size() << "\n";
    for(i = 0; i < contor;i++)
    {
        fout << sol[i] <<" ";
    }*/

}