Cod sursa(job #3209883)

Utilizator alex_0747Gheorghica Alexandru alex_0747 Data 3 martie 2024 18:49:45
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#define N 1000000
#define P 123457
#define Q 666013
using namespace std;

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

string s, t;
unordered_map <long long, bool> M;
int n, m;

void Hash()
{
    int i, x1, x2;
    x1 = x2 = 0;
    for (i = 0; i < m; i++)
    {
        x1 = (x1 * 3 + t[i] - 'a') % P;
        x2 = (x2 * 3 + t[i] - 'a') % Q;
    }
    M[1ll * x1 * N + 1ll * x2] = 1;
}

void Rez()
{
    int i, x1, x2, p1, p2, nr_poz;
    x1 = x2 = nr_poz = 0;
    for (i = 0; i < m; i++)
    {
        x1 = (x1 * 3 + s[i] - 'a') % P;
        x2 = (x2 * 3 + s[i] - 'a') % Q;
    }
    for (i = p1 = p2 = 1; i < m; i++)
    {
        p1 = p1 * 3 % P;
        p2 = p2 * 3 % Q;
    }
    nr_poz += M[1ll * x1 * N + 1ll * x2];
    for (; i < n; i++)
    {
        x1 = (x1 - (s[i - m] - 'a') * p1 % P + P) % P;
        x2 = (x2 - (s[i - m] - 'a') * p2 % Q + Q) % Q;
        x1 = (x1 * 3 + s[i] - 'a') % P;
        x2 = (x2 * 3 + s[i] - 'a') % Q;
        nr_poz += M[1ll * x1 * N + 1ll * x2];
    }
    fout << nr_poz << "\n";
}

int main()
{
    fin >> s;
    n = s.length();
    while (fin >> t)
    {
        m = t.length();
        Hash();
    }
    Rez();
    fout.close();
    return 0;
}