Cod sursa(job #2004143)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 25 iulie 2017 00:49:44
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 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];
string T, P;
vector <LL> B;

int cautbin1(int X)
{
    int be=1, en=L2;
    int mid, ans=0;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (B[mid]<=X)
        {
            be=mid+1;
            ans=mid;
        }
        else
          en=mid-1;
    }
    return ans;
}

int cautbin2(int X)
{
    int be=1, en=L2;
    int mid, ans=-1;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (B[mid]>=X)
        {
            en=mid-1;
            ans=mid;
        }
        else
          be=mid+1;
    }
    return 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;
    }
    nr=0;
    P1=1;
    for (i=M-1; i>=0; i--)
    {
        nr+=P1*(T[i]-'a');
        if (i>0)
          P1*=3;
    }
    B.push_back(-1);
    B.push_back(nr);
    L2++;
    for (i=M; i<N; i++)
    {
        nr-=P1*(T[i-M]-'a');
        nr*=3;
        nr+=T[i]-'a';
        B.push_back(nr);
        L2++;
    }
    A[0]=-1;
    sort(A+1, A+L1+1);
    sort(B.begin(), B.end());
    for (i=1; i<=L1; i++)
      if (A[i]!=A[i-1])
        ANS+=cautbin1(A[i])-cautbin2(A[i])+1;
    fout << ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}