Cod sursa(job #955258)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 31 mai 2013 10:46:03
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<fstream>
#include <iostream>
#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 <long long> has[mod];
int n, N, val[25], vect[MAXN], l;
long long sol, sum, put;

long long putere(long long p, long long 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;
}

long long baza_10()
{
    int i;
    long long nr_10 = 0, j=1;
    j = put;
    for(i=0; i<n; ++i, j/= 3)
        nr_10 += val[i]*j;
    return nr_10;
}

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

bool cautare(int aux, 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()
{
    long long aux, 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, 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;
}