Cod sursa(job #1369923)

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

using namespace std;

#define MOD 666013
#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 transforma(string x)
{
    long long p = 1, rez = 0;

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

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;
}

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()
{
    citire();

    L = a.size();

    int rez = 0;
    for(int i = 0; i <= L - l; i++)
    {
        string x;
        for(int j = i; j < i + l; j++)
            x += a[j];

        if(cauta(transforma(x)))
            rez++;
    }

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