Pagini recente » Cod sursa (job #1470397) | Profil RazBet | Cod sursa (job #2131666) | Cod sursa (job #2297281) | Cod sursa (job #2004143)
#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;
}