Cod sursa(job #2901425)

Utilizator stefanchpStefan Chiper stefanchp Data 13 mai 2022 18:17:08
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
#include <unordered_map>
#define N 100000
using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

unordered_map<long long, long long> M;
string text, aux;

long long conversie(string s, long long p)
{
    long long nrb3 = 0;
    int lg = s.size();
    for (int i = 0; i < lg; i++)
        nrb3 += (s[i] - 'a') * p, p /= 3;
    return nrb3;
}

int main()
{
    long long nrb3 = 0;
    long long p = 1, p2;

    fin >> text;
    fin >> aux;
    int lg = aux.size();
    for (int i = 1; i < lg; i++)
        p *= 3;
    p2 = p;
    for (int i = 0; i < lg; i++)
        nrb3 += (text[i]-'a') * p, p /= 3;
    M[nrb3] = 1;
    
    for (int i = 1; i < text.size() - lg + 1; i++)
    {
        nrb3 = (nrb3 - (text[i - 1] - 'a') * p2) * 3 + (text[i + lg - 1] - 'a');
        if (M.find(nrb3) == M.end())
            M[nrb3] = 1;
        else M[nrb3]++;
    }
    long long sol = 0;
    long long aux1;
    aux1 = conversie(aux, p2);
    if (M.find(aux1) != M.end()) sol += M[aux1], M.erase(aux1);
    while (fin >> aux)
    {
        aux1 = conversie(aux, p2);
        if (M.find(aux1) != M.end()) sol += M[aux1], M.erase(aux1);
    }
    fin.close();
    fout<<sol;
    fout.close();
    return 0;
}