Cod sursa(job #1831310)

Utilizator maryan_lupMarian Lupascu maryan_lup Data 17 decembrie 2016 20:18:14
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
#define FOR(i, a, b) for(unsigned i = a; i < b; i++)
#define M 319993 // nr.prim circular :)
using namespace std;

vector<unsigned long long> h[M];

int cautare(unsigned long long x)
{
    unsigned aux = x % M;
    FOR(i, 0, h[aux].size())
        if(h[aux][i] == x)
            return 1;
    return 0;
}

void inserare(unsigned long long x)
{
    unsigned aux = x % M;
    h[aux].push_back(x);
}

int main()
{
    ifstream in("abc2.in");
    ofstream out("abc2.out");

    char s[1000001], c[30];
    unsigned long long p[30], aux = 0;
    unsigned n, len = 0, sol = 0;
    p[0] = 1;

    FOR(i, 1, 21)
        p[i] = p[i-1] * 7;

    in >> s;
    n = strlen(s);
    while(in >> c)
    {
        if(!len)
            len = strlen(c);
        aux = 0;
        FOR(i, 0, len)
            aux += p[i] * (c[i] - 'a');
        inserare(aux);
    }
    aux = 0;
    FOR(i, 0, len)
        aux += p[i] * (c[i] - 'a');
    if(cautare(aux))
        sol++;
    FOR(i, len, n)
    {
        aux /= 7;
        aux += p[len - 1] * (s[i] - 'a');
        if(cautare(aux))
            sol++;
    }
    out << sol;
    return 0;
}