Cod sursa(job #1370347)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 3 martie 2015 14:01:21
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstring>
#include <fstream>

#define N 20000000
#define C 50001
#define MOD 8388593

using namespace std;

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

char a[N], c[22];
int la, lc;
unsigned int p[22];

unsigned int h[C], urm[C], lst[MOD], nr = 0;

inline bool cauta(unsigned int x)
{
    int r = x % MOD;
    for(int i = lst[r]; i; i = urm[i])
        if(x == h[i])
            return 1;
    return 0;
}

inline void adauga(unsigned int x)
{
    if(cauta(x))
        return;

    int r = x % MOD;
    h[++nr] = x;
    urm[nr] = lst[r];
    lst[r] = nr;
}

int main()
{
    p[0] = 1;
    for(int i = 1; i < 22; i++)
        p[i] = p[i - 1] * 3;

    in >> a;
    la = strlen(a);

    while(in >> c)
    {
        lc = strlen(c);
        unsigned int x = 0;
        for(int i = 0; i < lc; i++)
            x += p[i] * (c[i] - 'a');
        adauga(x);
    }

    int rez = 0;
    unsigned int x = 0;
    if(lc > la)
    {
        out << 0 << '\n';
        return 0;
    }

    for(int i = 0; i < lc; i++)
        x += p[i] * (a[i] - 'a');
    rez += cauta(x);

    for(int i = lc; i < la; i++)
    {
        x /= 3;
        x += p[lc - 1] * (a[i] - 'a');
        rez += cauta(x);
    }

    out << rez << '\n';
    return 0;
}