Cod sursa(job #2004140)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 25 iulie 2017 00:09:00
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <algorithm>
#include <map>
#include <vector>
#define MOD 30103
#define LL long long

using namespace std;

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

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

int main()
{
    fin >> T;
    N=T.size();
    while (fin >> P)
    {
        M=P.size();
        nr=0;
        P1=1;
        for (i=M-1; i>=0; i--)
        {
            nr+=P1*(P[i]-'a');
            if (i>0)
              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++;
    }
    fout << ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}