Cod sursa(job #1370089)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 3 martie 2015 12:56:05
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstring>
#include <fstream>

using namespace std;

#define MOD 8388593
#define N 50001

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

string a;
long long v[N]; int urm[N], lst[MOD], nr = 0;
int L, l;
long long p[20];

inline long long transforma(string x)
{
    long long rez = 0;

    for(int i = 0; i < l; i++)
        rez += p[i] * (x[i] - 'a');
    return rez;
}

inline int cauta(long long x)
{
    int r = x % MOD;
    for(int p = lst[r]; p; p = urm[p])
        if(v[p] == x)
            return 1;
    return 0;
}

inline void adauga(long long x)
{
    if(cauta(x))
        return;

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

void citire()
{
    getline(in, a);

    string x;
    bool ok = 0;
    while(getline(in, x))
    {
        if(!ok)
        {
            ok = 1;
            l = x.size();
        }
        adauga(transforma(x));
    }
}

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

    citire();

    L = a.size();

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

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

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