Cod sursa(job #2417679)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 30 aprilie 2019 20:15:42
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>
#define lld long long
#define mod 10007
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
class lst
{
private:
    struct nod
    {
        nod *urm;
        unsigned int value;
        nod(unsigned int v)
        {
            urm = 0;
            value = v;
        }
    };
    nod *root;
public:
    lst()
    {
        root = 0;
    }
    void add(unsigned int v)
    {
        nod *nw = new nod(v);
        if (!root)
        {
            root = nw;
            return;
        }
        nw -> urm = root;
        root = nw;
    }
    bool exists(unsigned int v)
    {
        if (!root) return false;
        nod *act = root;
        while (act)
        {
            if(act->value == v) return true;
            act = act->urm;
        }
        return false;
    }
};
lst dispersionTable[mod+1];
char s[10000005], p[25];
int ln,lp, ans;
unsigned int wh;
unsigned int hsh, pw[25];
const unsigned int pww = 3;
int main()
{
    fin>>s;
    pw[0] = 1;
    for (int i=1; i<20; ++i)
        pw[i] = pw[i-1] * pww;
    fin>>p;
    lp = strlen(p);
    do
    {
        hsh = 0;
        for (int i=lp-1; i>=0; --i)
            hsh =  hsh + (p[i]-'a')*pw[lp-i-1];
        wh = hsh % mod;
        if (!dispersionTable[wh].exists(hsh))
            dispersionTable[wh].add(hsh);
    }
    while (fin>>p);
    hsh = 0;
    for (int i=lp-1; i>=0; --i)
    {
        s[i]-='a';
        hsh = hsh + s[i]*pw[lp-i-1];
    }
    wh = hsh % mod;
    if (dispersionTable[wh].exists(hsh))++ans;
    for (int i=lp; s[i]; ++i)
    {
        s[i]-='a';
        hsh = (hsh - s[i-lp]*pw[lp-1]) *pww + s[i];
        wh = hsh%mod;
        if (dispersionTable[wh].exists(hsh))++ans;
    }
    fout<<ans<<'\n';
    return 0;
}