Cod sursa(job #2004128)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 24 iulie 2017 23:26:33
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define MOD1 30103
#define MOD2 666013

using namespace std;

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

int N, M, i, j, ANS;
int P1, P2, nr1, nr2;
vector <int> Hash[MOD1];
string T, P;

void Check(int A, int B)
{
    if (find(Hash[A].begin(), Hash[A].end(), B)!=Hash[A].end())
      ANS++;
}

int main()
{
    fin >> T;
    N=T.size();
    while (fin >> P)
    {
        M=P.size();
        nr1=nr2=0;
        P1=P2=1;
        for (i=M-1; i>=0; i--)
        {
            nr1+=P1*(P[i]-'a');
            nr1%=MOD1;
            nr2+=P2*(P[i]-'a');
            nr2%=MOD2;
            if (i>0)
            {
                P1*=3;
                P1%=MOD1;
                P2*=3;
                P2%=MOD2;
            }
        }
        Hash[nr1].push_back(nr2);
    }
    nr1=nr2=0;
    P1=P2=1;
    for (i=M-1; i>=0; i--)
    {
        nr1+=P1*(T[i]-'a');
        nr1%=MOD1;
        nr2+=P2*(T[i]-'a');
        nr2%=MOD2;
        if (i>0)
        {
            P1*=3;
            P1%=MOD1;
            P2*=3;
            P2%=MOD2;
        }
    }
    Check(nr1, nr2);
    for (i=M; i<N; i++)
    {
        nr1-=P1*(T[i-M]-'a');
        nr1%=MOD1;
        if (nr1<0)
          nr1=MOD1+nr1;
        nr1*=3;
        nr1+=T[i]-'a';
        nr1%=MOD1;
        nr2-=P2*(T[i-M]-'a');
        nr2%=MOD2;
        if (nr2<0)
          nr2=MOD2+nr2;
        nr2*=3;
        nr2+=T[i]-'a';
        nr2%=MOD2;
        Check(nr1, nr2);
    }
    fout << ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}