Cod sursa(job #2417680)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 30 aprilie 2019 20:19:32
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>
#define lld long long
#define mod 10007
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
vector<unsigned int>dt[mod+1];
char s[10000005], p[25];
int ln,lp, ans;
unsigned int wh;
unsigned int hsh, pw[25];
const unsigned int pww = 3;
bool ok;
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;
        ok = false;
        for (int j=0; j<dt[wh].size(); ++j)
            if (dt[wh][j] == hsh)
            {
                ok = true;
                break;
            }
        if (!ok)
            dt[wh].push_back(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;
    for (int j=0; j<dt[wh].size(); ++j)
        if (dt[wh][j] == hsh)
        {
            ++ans;
            break;
        }
    for (int i=lp; s[i]; ++i)
    {
        s[i]-='a';
        hsh = (hsh - s[i-lp]*pw[lp-1]) *pww + s[i];
        wh = hsh%mod;
        for (int j=0; j<dt[wh].size(); ++j)
            if (dt[wh][j] == hsh)
            {
                ++ans;
                break;
            }
    }
    fout<<ans<<'\n';
    return 0;
}