Cod sursa(job #955643)

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

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

const int MAXN = 10000010, mod = 1257;
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 nr)
{
    if(p == 0)
        return 1;
    if(p == 1)
        return nr;
    int x = putere(p/2, nr);
    if(p%2 == 0)
        return x*x;
    else
        return x*x*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=1; i<20; ++i)
        aux *= 3;
    fout << aux << "\n\n";
    */

    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, 3);
        }
        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);
    }


    for(i=0; i+n<N; ++i)
    {
        sum = baza10(i);
        aux = sum%mod;
        aux1 = cautare(aux, sum);
        if(aux1 == 1)
            ++sol;
    }
    fout << sol;

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

    return 0;
}