Cod sursa(job #2417607)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 30 aprilie 2019 15:28:42
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <unordered_map>
#include <fstream>
#include <iostream>
#include <string>
#define lld long long
#define mod 1000000007
using namespace std;
//FILE *fin=fopen("abc2.in","r");
ifstream fin("abc2.in");
FILE *fout=fopen("abc2.out","w");
unordered_map<string,int>ump;
string s, sact;
const lld pww = 31;
int ans, ln, n;
lld pw[20], expectedHash, currHash;
bool check(string sact)
{
    n = sact.size();
    if (n > ln) return 0;
    expectedHash = currHash = 0LL;
    for (int i=0; i<n; ++i)
    {
        expectedHash = (expectedHash + sact[i] * pw[n - i - 1]) % mod;
        currHash = (currHash + s[i] * pw[n - i - 1]) % mod;
    }
    if (currHash == expectedHash) return true;
    for (int i=n; i<ln; ++i)
    {
        currHash = (currHash - s[i - n] * pw[n-1]) % mod;
        if (currHash < 0) currHash = mod + currHash;
        currHash = (currHash * pww + s[i]) % mod;
        if (currHash == expectedHash) return true;
    }
    return false;
}
int main()
{
    fin>>s;
    ln = s.size();
    pw[0] = 1;
    for (int i=1; i<20; ++i)
        pw[i] = ( pw[i-1] * pww ) % mod;
    while(fin>>sact)
        ++ump[sact];
    for (auto x:ump)
        if (check(x.first))
            ++ans;
    fprintf(fout,"%d\n",ans);
    return 0;
}