Cod sursa(job #3159745)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 21 octombrie 2023 21:50:27
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 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;

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;
        }

        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(ap.count(hsh))
        ans++;
    for(int i=lg; i<n; i++) {
        hsh -= (c[i-lg] - 'a' + 1) * p;
        hsh *= 4;
        hsh += c[i] - 'a' + 1;

        if(ap.count(hsh))
            ans++;
    }

    out << ans;
    return 0;
}