Cod sursa(job #1482457)

Utilizator aaron72Armand Ioan Anusca Popa aaron72 Data 7 septembrie 2015 11:33:52
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>
#define Q 17
#define P 123457
#define R 300007

using namespace std;

vector <int> h[P+3];
char text[10000004];
int e[23], f[23];

void Init()
{
    int i;
    e[0] = f[0] = 1;
    for (i = 1; i <= 21; i++)
    {
        e[i] = (e[i - 1] * Q) % P;
        f[i] = (f[i - 1] * Q) % R;
    }
}

inline void Adauga(int x, int val)
{
    h[x].push_back(val);
}

inline int Cauta(int x, int val)
{
    for (unsigned i = 0; i < h[x].size(); i++)
        if (h[x][i] == val) return i;
    return -1;
}

void Sterge(int r, int y)
{
    int i, L;
    L = h[r].size();
    i = Cauta(r, y);
    if (i != -1)
    {
        h[r][i] = h[r][L-1];
        h[r].pop_back();
    }
}

int main()
{
    int x, y, i, j, L, PQ, RQ, cnt;
    string s;

    Init();

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

    fin >> text;
    /// creare hash
    while (fin >> s)
    {
        x = y = 0;
        L = s.length();
        for (i = 0; i < L; i++)
        {
            j = s[i] - 'a';
            x = (x * Q + j) % P;
            y = (y * Q + j) % R;
        }
        i = Cauta(x, y);
        if (i == -1) Adauga(x, y);
    }
    PQ = e[L - 1];
    RQ = f[L - 1];
    ///creare primul numar
    x = y = 0;
    for (i = 0; i < L; i++)
    {
            j = text[i] - 'a';
            x = (x * Q + j) % P;
            y = (y * Q + j) % R;
    }
    cnt = 0;
    i = Cauta(x, y);
    if (i > -1)
        cnt++;
    for (i = L; text[i]; i++)
    {
        ///hash1 = ((hash1-(B[i-NA]*P1)%MOD1 + MOD1) * P + B[i]) % MOD1;
        x = ((x-((text[i-L] - 'a') * PQ) % P + P)*Q + (text[i]-'a')) % P;
        y = ((y-((text[i-L] - 'a') * RQ) % R + R)*Q + (text[i]-'a')) % R;
        j = Cauta(x, y);
        if (j > -1)
            cnt++;
    }
    fout << cnt << "\n";
    fin.close();
    fout.close();
    return 0;
}