Cod sursa(job #955670)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 1 iunie 2013 12:12:49
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int MAXN = 10000010, mod = 662013;
char v[MAXN], v1[25];
vector <unsigned int> has[mod];
int n, N, val[25], vect[MAXN], l;
long long sol;
unsigned int sum, put;

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 += val[i]*j;
    return nr_10;
}

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

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

int main()
{
    unsigned int aux=1, aux1, i;
    fin.getline(v, MAXN);
    N = strlen(v);

    for(i=0; i<N; ++i)
    {
        if(v[i] == 'a')
            vect[i] = 0;
        else if(v[i] == 'b')
            vect[i] = 1;
        else
            vect[i] = 2;
    }

    while(fin.getline(v1, 25))
    {
        if(n == 0){
            n = strlen(v1);
            put = putere(n-1);
        }
        for(i=0; i<n; ++i)
        {
            if(v1[i] == 'a')
                val[i] = 0;
            else if(v1[i] == 'b')
                val[i] = 1;
            else
                val[i] = 2;
        }
        aux1 = baza_10();
        aux = aux1%mod;
        has[aux].push_back(aux1);
    }


    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 + vect[i+n-1];
        aux = sum%mod;
        aux1 = cautare(aux, sum);
        if(aux1 == 1)
            ++sol;
    }
    fout << sol;

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

    return 0;
}