Cod sursa(job #2004279)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 25 iulie 2017 14:32:07
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#define MOD 30103
#define VAL 10000005
#define DIM 25
#define LL unsigned int

using namespace std;

int N, M, i, j, ANS;
LL nr, P1, K;
char T[VAL], P[DIM];
vector <LL> Hash[MOD];

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    fgets(T, VAL, stdin);
    N=strlen(T)-1;
    while (fgets(P, DIM, stdin))
    {
        M=strlen(P)-1;
        nr=0;
        P1=1;
        for (i=M-1; i>=0; i--)
        {
            nr+=P1*(P[i]-'a');
            P1*=3;
        }
        K=nr % MOD;
        Hash[K].push_back(nr);
    }
    nr=0;
    P1=1;
    for (i=M-1; i>=0; i--)
    {
        nr+=P1*(T[i]-'a');
        if (i>0)
          P1*=3;
    }
    K=nr % MOD;
    if (find(Hash[K].begin(), Hash[K].end(), nr)!=Hash[K].end())
      ANS++;
    for (i=M; i<N; i++)
    {
        nr-=P1*(T[i-M]-'a');
        nr*=3;
        nr+=T[i]-'a';
        K=nr % MOD;
        if (find(Hash[K].begin(), Hash[K].end(), nr)!=Hash[K].end())
          ANS++;
    }
    printf("%d\n", ANS);
    return 0;
}