Cod sursa(job #1834200)

Utilizator raulmuresanRaul Muresan raulmuresan Data 24 decembrie 2016 01:56:29
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
//Algoritmul lui Rabin Karp
#include<fstream>
#include<vector>
#include<string>
#define P 73
#define MOD1 200003

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,hash2contor,sol ,trei[50];
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)
{
    hash1 =  0;
    for(i = 0; i < m ; i++)
    {
        hash1 = hash1 + trei[i] * (w[i] - 'a');
    }
    if(cauta(hash1) == 0)
        adauga(hash1);
}


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

    cauta(b);

    while(fin >> sir)
    {
        cauta(sir);
    }
    hash1 = 0;
    for(i = 0; i < m ; i++)
    {
        hash1 = hash1 + (a[i] - 'a') * trei[i];
    }
    sol += cauta(hash1);
    for(i = m ; i < n; i++)
    {
        hash1 = hash1 / 3;
        hash1 = hash1 + ((a[i] - 'a') * trei[m - 1]);
        sol += cauta(hash1);
    }


    fout << sol <<"\n";

}