Cod sursa(job #2417676)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 30 aprilie 2019 20:02:29
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.74 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<unsigned int>dispersionTable[mod+1];
char s[10000005], p[25];
int ln,lp, ans;
unsigned int wh;
unsigned int hsh, pw[25];
const unsigned int pww = 3;
void add()
{
    wh = hsh % mod;
    for (int i=0; i<dispersionTable[wh].size(); ++i)
        if (dispersionTable[wh][i] == hsh) return;
    dispersionTable[wh].push_back(hsh);
}
bool findd()
{
    wh = hsh % mod;
    for (int i=0; i<(int)dispersionTable[wh].size(); ++i)
        if(dispersionTable[wh][i] == hsh) 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] = pw[i-1] * pww;
    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];
        add();
    }
    while (fscanf(fin,"%s\n",p)!=EOF);
    hsh = 0;
    for (int i=lp-1; i>=0; --i)
    {
        s[i]-='a';
        hsh = hsh + s[i]*pw[lp-i-1];
    }
    if (findd())++ans;
    for (int i=lp; s[i]; ++i)
    {
        s[i]-='a';
        hsh = (hsh - s[i-lp]*pw[lp-1]) *pww + s[i];
        if (findd())++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;
}
*/