Cod sursa(job #908693)

Utilizator FayedStratulat Alexandru Fayed Data 9 martie 2013 22:01:01
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <cstring>
#include <vector>
#define Hmod 666013
using namespace std;

vector<unsigned int> H[Hmod];
char text[10000000];

inline short search(unsigned int x)
{
    const unsigned int m = x%Hmod;
    vector<unsigned int>::iterator i=H[m].begin(), stop=H[m].end();
    while (i != stop)
    {
        if (*i == x)
            return 1;
        ++i;
    }
    return 0;
}

inline unsigned int hash(char *cuv, unsigned int l)
{
    unsigned int val=0, i;
    for (i=0; i<l; ++i)
        val = (val*3 + cuv[i]-'a');
    return val;
}

int main()
{
    ifstream in("abc2.in"); ofstream out("abc2.out");
    char cuv[20];
    unsigned int i, l, cnt=0, val, n, g=1;

    in>>text>>cuv;
    l = strlen(cuv);
    val = hash(cuv, l);
    H[val%Hmod].push_back(val);
    while (in>>cuv)
    {
        val = hash(cuv, l);
        H[val%Hmod].push_back(val);
    }

    for (i=1; i<l; ++i)
        g *= 3;

    val = hash(text, l);
    cnt += search(val);
    n = strlen(text);

    for (i=l; i<n; ++i)
    {
        //val = ((val - ((text[i-l]-'a')*g)%Hmod + Hmod)*3 + text[i]-'a')%Hmod;
        val = (val - (text[i-l]-'a')*g)*3 + text[i]-'a';
        cnt += search(val);
    }

    out<<cnt;
    return 0;
}