Cod sursa(job #2818972)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 17 decembrie 2021 14:55:51
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <cstring>
#include <set>

#define modh myHash % mod

using namespace std;

const int base = 3, mod = 30007;
int ans;
char s[10000010], cuv[30];
set <unsigned int> dictionar[mod];

int len, s_len;
unsigned int base_pow;

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    fgets(s,10000005,stdin);
    s_len = strlen(s) - 1;
    fgets(cuv,25,stdin);
    len = strlen(cuv) - 1;
    unsigned int myHash = 0;
    for(int i = 0; i < len; i++)
        myHash = myHash * base + (cuv[i] - 'a');
    if(dictionar[modh].find(myHash) == dictionar[modh].end())
        dictionar[modh].insert(myHash);
    while(!feof(stdin))
    {
        fgets(cuv,25,stdin);
        len = strlen(cuv) - 1;
        myHash = 0;
        for(int i = 0; i < len; i++)
            myHash = myHash * base + (cuv[i] - 'a');
        if(dictionar[modh].find(myHash) == dictionar[modh].end())
            dictionar[modh].insert(myHash);
    }
    base_pow = 1;
    for(int i = 1; i < len; i++)
        base_pow *= base;
    myHash = 0;
    for(int i = 0; i < len; i++)
        myHash = myHash * base + (s[i] - 'a');
    if(dictionar[modh].find(myHash) != dictionar[modh].end())
        ans++;
    for(int i = len; i < s_len; i++)
    {
        int val = s[i - len] - 'a';
        myHash = myHash - base_pow * val ;
        myHash = myHash * base + (s[i] - 'a');
        if(dictionar[modh].find(myHash) != dictionar[modh].end())
            ans++;
    }
    printf("%u\n", ans);
    return 0;
}