Cod sursa(job #3209885)

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

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

string s, t;
set <long long> S;
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;
    }
    S.insert(1LL * x1 * N + 1LL * x2);
}

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;
    }
    if (S.find(1LL * x1 * N + 1LL * x2) != S.end())
        nr_poz++;
    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;
        if (S.find(1LL * x1 * N + 1LL * x2) != S.end())
            nr_poz++;
    }
    fout << nr_poz << "\n";
}

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