Cod sursa(job #957725)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 5 iunie 2013 21:38:37
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int MAXN = 10000010, MOD = 666013;

char v[MAXN], v1[25];
vector <unsigned int> has[MOD];
int n, N, l;
long long sol;
unsigned int sum, put, aux1;

unsigned int putere(unsigned int p)
{
    unsigned int i, nr=1;
    for(i=0; i<p; ++i)
        nr *= 3;
    return nr;
}

unsigned int baza_10()
{
    int i;
    unsigned int nr_10 = 0, j;
    j = put;
    for(i=0; i<n; ++i, j/= 3)
        nr_10 += (v1[i] - 'a')*j;
    return nr_10;
}

unsigned int baza10(int i)
{
    unsigned int nr_10=0, j;
    int k;
    j = put;
    for(k=i; k<i+n; ++k, j/= 3)
        nr_10 += (v[k] - 'a')*j;
    return nr_10;
}

inline bool cautare(int aux, unsigned int val)
{
    int i, j = has[aux].size();
    for(i=0; i<j; ++i)
        if(has[aux][i] == val)
            return 1;
    return 0;
}

inline void adauga(unsigned int aux)
{
    has[aux].push_back(aux1);
}

int main()
{
    unsigned int aux=1, i;
    fin >> v;
    N = strlen(v);

    while(fin >> v1)
    {
        if(n == 0){
            n = strlen(v1);
            put = putere(n-1);
        }
        aux1 = baza_10();
        aux = aux1%MOD;
        adauga(aux);
    }


    sum = baza10(0);
    aux = sum%MOD;
    aux1 = cautare(aux, sum);
    if(aux1 == 1)
        ++sol;
    for(i=1; i+n<=N; ++i)
    {
        sum = (sum%put)*3 + (v[i+n-1] - 'a');
        aux = sum%MOD;
        aux1 = cautare(aux, sum);
        if(aux1 == 1)
            ++sol;
    }
    fout << sol;

    fin.close();
    fout.close();

    return 0;
}