Cod sursa(job #2417698)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 30 aprilie 2019 20:53:15
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
#pragma GCC optimize("03")
#define lld long long
#define mod 8191
using namespace std;
FILE *fin=fopen("abc2.in","r");
FILE *fout=fopen("abc2.out","w");
vector<unsigned int>dt[mod];
char s[10000015], p[25];
int lp, ans;
int i, j;
int wh;
bool ok;
unsigned int hsh, pw[25];
int main()
{
    fscanf(fin,"%s\n",s);
    pw[0] = 1;
    for (i=1; i<20; ++i)
        pw[i] = pw[i-1] * 3;
    fscanf(fin,"%s\n",p);
    lp = strlen(p);
    do
    {
        hsh = 0;
        for (i=0; i<lp; ++i)
            hsh = hsh + (p[i]-'a') * pw[i];
        wh = hsh % mod;
        ok = false;
        for (j=0;j<dt[wh].size();++j)
            if (dt[wh][j] == hsh)
        {
            ok = true;
            break;
        }
        if(!ok)
            dt[wh].push_back(hsh);
    }
    while ((fscanf(fin,"%s\n",p))!=EOF);
    hsh = 0;
    for (i=0; i<lp; ++i)
        hsh = hsh + (s[i]-'a')*pw[i];
    wh = hsh % mod;
    for (j=0; j<dt[wh].size(); ++j)
        if (dt[wh][j] == hsh)
        {
            ++ans;
            break;
        }
    for (i=lp; s[i]; ++i)
    {
        hsh = hsh / 3 + (s[i]-'a')*pw[lp-1];
        wh = hsh%mod;
        for (j=0; j<dt[wh].size(); ++j)
            if (dt[wh][j] == hsh)
            {
                ++ans;
                break;
            }
    }
    fprintf(fout,"%d\n",ans);
    return 0;
}