Cod sursa(job #3159742)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 21 octombrie 2023 21:40:17
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <cstring>
#include <unordered_map>

using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
typedef long long ll;
const int N = 1e7 + 5, mod = 1e9 + 7;

int n, lg, ans;
ll hsh, p;
char c[N], cuv[25];
unordered_map<ll, bool> ap;

int main()
{
    in >> c;
    while(in >> cuv) {
        lg = strlen(cuv);
        hsh = 0;
        for(int i=0; i<lg; i++) {
            hsh *= 4;
            hsh += cuv[i] - 'a' + 1;
            if(hsh >= mod)
                hsh %= mod;
        }

        ap[hsh] = 1;
    }

    n = strlen(c);
    hsh = 0;
    p = 1;
    for(int i=0; i<lg; i++) {
        hsh *= 4;
        if(i < lg - 1)
            p *= 4;
        hsh += c[i] - 'a' + 1;
        if(hsh >= mod)
            hsh %= mod;
        if(p >= mod)
            p %= mod;
    }
    ans += ap[hsh];
    for(int i=lg; i<n; i++) {
        hsh -= (c[i-lg] - 'a' + 1) * p;
        hsh += mod;
        hsh %= mod;
        hsh *= 4;
        hsh += c[i] - 'a' + 1;
        hsh %= mod;

        ans += ap[hsh];
    }

    out << ans;
    return 0;
}