Cod sursa(job #2417683)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 30 aprilie 2019 20:29:10
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>
#define lld long long
#define mod 100007
using namespace std;
FILE *fin=fopen("abc2.in","r");
FILE *fout=fopen("abc2.out","w");
vector<unsigned int>dt[mod+1];
char s[10000005], p[25];
int add[255];
int ln,lp, ans;
int i, j;
unsigned int wh;
unsigned int hsh, pw[25];
const unsigned int pww = 3;
bool ok;
int main()
{
    fscanf(fin,"%s\n",s);
    add['a'] = 0;
    add['b'] = 1;
    add['c'] = 2;
    pw[0] = 1;
    for (i=1; i<20; ++i)
        pw[i] = pw[i-1] * pww;
    fscanf(fin,"%s\n",p);
    lp = strlen(p);
    do
    {
        hsh = 0;
        for (i=lp-1; i>=0; --i)
            hsh =  hsh + add[p[i]]*pw[lp-i-1];
        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=lp-1; i>=0; --i)
        hsh = hsh + add[s[i]]*pw[lp-i-1];
    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 - add[s[i-lp]]*pw[lp-1]) *pww + add[s[i]];
        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;
}