Cod sursa(job #3210916)

Utilizator PiciuAndreiAlinPiciu Andrei Alin PiciuAndreiAlin Data 7 martie 2024 18:24:03
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
#define P 123457
#define Q 666013
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");

string a, b;
int n, m, k, cnt;
unordered_map<long long, bool>M;
int main()
{
    ios_base::sync_with_stdio(0);
    fin.tie(0);
    fout.tie(0);
    int i;
    long long x1, x2, p, p1;
    fin >> a;
    fin.get();
    while(fin >> b)
    {
        x1 = x2 = 0;
        m = b.length();
        for(i = 0; i < m; i++)
        {
            x1 = (x1 * 3 + (b[i] - 'a')) % P;
            x2 = (x2 * 3 + (b[i] - 'a')) % Q;
        }
        M[x1] = 1;
        M[x2] = 1;
        fin.get();
    }
    m = b.length();
    n = a.length();
    p = p1 = 1;
    for(i = 1; i < m; i++)
    {
        p = (p * 3) % P;
        p1 = (p1 * 3) % Q;
    }
    x1 = 0;
    x2 = 0;
    for(i = 0; i < m; i++)
    {
        x1 = (x1 * 3 + (a[i] - 'a')) % P;
        x2 = (x2 * 3 + (a[i] - 'a')) % Q;
    }
    if(M[x1] == 1 and M[x2] == 1)cnt++;
    for(i = m; i < n; i++)
    {
        x1 = (x1 - (a[i - m] - 'a') * p % P + P) % P;
        x1 = (x1 * 3 + (a[i] - 'a')) % P;
        x2 = (x2 - (a[i - m] - 'a') * p1 % Q + Q) % Q;
        x2 = (x2 * 3 + (a[i] - 'a')) % Q;
        if(M[x1] == 1 and M[x2] == 1)cnt++;
    }
    fout << cnt;
    return 0;
}