Cod sursa(job #1837068)

Utilizator d0rina2011Craciun Dorina d0rina2011 Data 28 decembrie 2016 23:08:39
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <vector>
#define M 666013

using namespace std;

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

vector <unsigned int> h[M];
char s[10000001], cuv[50001];
long long v[25];//puterile lui 3

int caut(long long x){
    long long  y = x % M, i, s = h[y].size();
    for(i = 0; i < s; ++i){
        if(h[y][i] == x) return 1;
    }
    return 0;
}

int main()
{
    long long n, n1, aux, i, nr = 0;
    fin>>s;
    n = strlen(s);
    v[0] = 1;
    for(i = 1; i <= 19; i++)
        v[i] = v[i - 1] * 3;
    while(fin>>cuv){
        n1 = strlen(cuv);
        aux = 0;
        for(i = 0; i < n1; ++i){
            aux += v[i] * (cuv[i] - 'a');
        }
        h[aux % M].push_back(aux);
    }
    aux = 0;
    for(i = 0; i < n1; ++i){
        aux += v[i] * (s[i] - 'a');
    }
    nr += caut(aux);
    for(i = n1; i < n; i++){
        aux /= 3;
        aux += v[n1 - 1] * (s[i] - 'a');
        nr += caut(aux);
    }
    fout<<nr;
    return 0;
}