Cod sursa(job #1017400)

Utilizator poptibiPop Tiberiu poptibi Data 27 octombrie 2013 19:06:34
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const unsigned int LMAX = 10000005, MOD = 60001;

unsigned int N, M, Ans;
char S[LMAX], Q[25];
vector<unsigned int> Hash[MOD];

bool Find(unsigned int Val)
{
    unsigned int Key = Val % MOD;
    if(find(Hash[Key].begin(), Hash[Key].end(), Val) != Hash[Key].end()) return 1;
    return 0;
}

void Add(unsigned int Val)
{
    unsigned int Key = Val % MOD;
    if(!Find(Val)) Hash[Key].push_back(Val);
}

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    
    gets(S + 1);
    N = strlen(S + 1);
    S[0] = 'a';
    while(!feof(stdin))
    {
        gets(Q + 1);
        M = strlen(Q + 1);
        unsigned int Codif = 0;
        for(int i = 1; i <= M; ++ i)
            Codif = Codif * 3 + Q[i] - 'a';
        Add(Codif);
    }
    
    unsigned int P = 1, Codif = 0;
    for(int i = 1; i < M; ++ i) 
        Codif = Codif * 3 + S[i] - 'a', P *= 3;
    for(int i = 1; i <= N - M + 1; ++ i)
    {
        Codif = (Codif - (S[i - 1] - 'a') * P) * 3 + S[i + M - 1] - 'a';
        if(Find(Codif)) Ans ++;
    }
    
    printf("%i\n", Ans);
}