Cod sursa(job #3209580)

Utilizator mateilucaLuca Matei Gabriel mateiluca Data 2 martie 2024 21:24:08
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>
#define P 123457
#define Q 777013

using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
int cnt, L, n;
char text[10000005], cuv[25];
struct Cuvinte{
    int v1, v2;
}v[50005];
bool Cmp(Cuvinte A, Cuvinte B)
{
    if(A.v1 == B.v1)
        return A.v2 < B.v2;
    return A.v1 < B.v1;
}
int CautBin(int x, int y)
{
    int st, dr, mij;
    st = 1;
    dr = n;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij].v1 > x)
            dr = mij - 1;
        else if(v[mij].v1 < x)
                st = mij + 1;
        else{
            if(v[mij].v2 > y)
                dr = mij - 1;
            else if(v[mij].v2 < y)
                    st = mij + 1;
            else return 1;
        }
    }
    return 0;
}

int main()
{
    int i, x1, x2, p1, p2;
    fin >> text;
    while(fin >> cuv)
    {
        x1 = x2 = 0;
        for(i = 0;cuv[i] != 0;i++)
        {
            x1 = (x1 * 3 + cuv[i] - 'a') % P;
            x2 = (x2 * 3 + cuv[i] - 'a') % Q;
        }
        v[++n] = {x1, x2};
    }
    L = strlen(cuv);
    sort(v + 1, v + n + 1, Cmp);
    x1 = x2 = 0;
    p1 = p2 = 1;
    for(i = 1;i < L;i++)
    {
        p1 = p1 * 3 % P;
        p2 = p2 * 3 % Q;
    }
    for(i = 0;i < L;i++)
    {
        x1 = (x1 * 3 + text[i] - 'a') % P;
        x2 = (x2 * 3 + text[i] - 'a') % Q;
    }
    if(CautBin(x1, x2))
        cnt++;
    for(i = L;text[i] != 0;i++)
    {
        x1 = (x1 - p1 * (text[i - L] - 'a') + P) % P;
        x1 = (x1 * 3 + text[i] - 'a') % P;
        x2 = (x2 - p2 * (text[i - L] - 'a') + Q) % Q;
        x2 = (x2 * 3 + text[i] - 'a') % Q;
        if(CautBin(x1, x2))
            cnt++;
    }
    fout << cnt << "\n";
    fout.close();
    return 0;
}