Cod sursa(job #2004145)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 25 iulie 2017 01:02:59
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define MOD 63103
#define LL long long

using namespace std;

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

int N, M, i, j, ANS, K;
int L1, L2;
LL nr, P1;
LL A[MOD], B[MOD];
string T, P;

void Check(LL X)
{
    int be=1, en=L1;
    int mid, ans=0;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (A[mid]==X)
        {
            ans=1;
            break;
        }
        if (A[mid]<X)
          be=mid+1;
        else
          en=mid-1;
    }
    ANS+=ans;
}

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;
        }
        A[++L1]=nr;
    }
    sort(A+1, A+L1+1);
    nr=0;
    P1=1;
    for (i=M-1; i>=0; i--)
    {
        nr+=P1*(T[i]-'a');
        if (i>0)
          P1*=3;
    }
    Check(nr);
    for (i=M; i<N; i++)
    {
        nr-=P1*(T[i-M]-'a');
        nr*=3;
        nr+=T[i]-'a';
        Check(nr);
    }
    fout << ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}