Cod sursa(job #2417677)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 30 aprilie 2019 20:08:10
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>
#define lld long long
#define mod 10007
using namespace std;
FILE *fin=fopen("abc2.in","r");
FILE *fout=fopen("abc2.out","w");
class lst
{
private:
    struct nod
    {
        nod *urm;
        unsigned int value;
        nod(unsigned int v)
        {
            urm = 0;
            value = v;
        }
        nod()
        {
            value = 0;
            urm = NULL;
        }
    };
    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;
void add()
{
    wh = hsh % mod;
    if (!dispersionTable[wh].exists(hsh))
        dispersionTable[wh].add(hsh);
}
bool findd()
{
    wh = hsh % mod;
    return dispersionTable[wh].exists(hsh);
}
int main()
{
    //freopen("abc2.in","r",stdin);
    //freopen("abc2.out","w",stdout);
    fscanf(fin,"%s\n", s);
    pw[0] = 1;
    for (int i=1; i<20; ++i)
        pw[i] = pw[i-1] * pww;
    fscanf(fin,"%s\n",p);
    lp = strlen(p);
    do
    {
        hsh = 0;
        for (int i=lp-1; i>=0; --i)
            hsh =  hsh + (p[i]-'a')*pw[lp-i-1];
        add();
    }
    while (fscanf(fin,"%s\n",p)!=EOF);
    hsh = 0;
    for (int i=lp-1; i>=0; --i)
    {
        s[i]-='a';
        hsh = hsh + s[i]*pw[lp-i-1];
    }
    if (findd())++ans;
    for (int i=lp; s[i]; ++i)
    {
        s[i]-='a';
        hsh = (hsh - s[i-lp]*pw[lp-1]) *pww + s[i];
        if (findd())++ans;
    }
    fprintf(fout,"%d\n",ans);
    fclose(fin);
    fclose(fout);
    return 0;
}