Cod sursa(job #1370037)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 3 martie 2015 12:45:23
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 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];

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

    for(int i = l - 1; i >= 0; i--)
        rez += p[l - i - 1] * (x[i] - 'a');
    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)
{
    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;
    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;
}