Cod sursa(job #2417668)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 30 aprilie 2019 19:37:04
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 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");
vector<int>dispersionTable[mod+1];
char s[10000005], p[25];
int ln,lp, n, ans, wh;
int hsh, pw[21];
const int pww = 3;
void add(int x)
{
    wh = x % mod;
    for (int i=0; i<dispersionTable[wh].size(); ++i)
        if (dispersionTable[wh][i] == x) return;
    dispersionTable[wh].push_back(x);
}
bool findd(int x)
{
    wh = x % mod;
    for (int i=0; i<dispersionTable[wh].size(); ++i)
        if(dispersionTable[wh][i] == x) return true;
    return false;
}
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] = (1LL*pw[i-1] * pww) % mod;
    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] ) % mod;
        add(hsh);
    }
    while (fscanf(fin,"%s\n",p)!=EOF);
    hsh = 0;
    for (int i=0; i<lp; ++i)
        hsh = ( hsh + (s[i]-'a')*pw[lp-i-1]) % mod;
    if (findd(hsh))++ans;
    for (int i=lp; s[i]; ++i)
    {
        hsh = (hsh - (s[i-lp]-'a')*pw[lp-1]) % mod;
        if (hsh<0) hsh = mod + hsh;
        hsh = (hsh * pww + (s[i]-'a')) % mod;
        if (findd(hsh))++ans;
    }
    fprintf(fout,"%d\n",ans);
    fclose(fin);
    fclose(fout);
    return 0;
}
/* ?
#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;
}
*/