Pagini recente » Cod sursa (job #914848) | Cod sursa (job #1192672) | Cod sursa (job #1521478) | Istoria paginii runda/oji_training_0 | Cod sursa (job #1093104)
#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const int NMAX = 10000005;
const int DMAX = 25;
const int MOD = 100009;
int N,M,i,r; ll cod,B,sol;
char S[NMAX],A[DMAX];
vector<ll> V[MOD];
vector<ll>::iterator it;
void Add(long long x)
{
r=x%MOD;
V[r].push_back(x);
}
void Find(long long x)
{
r=x%MOD;
for(it=V[r].begin();it!=V[r].end();it++)
if(*it==x) {sol++; return;}
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(S+1,NMAX,stdin);
M=strlen(S+1)-1;
while(fgets(A+1,DMAX,stdin))
{
N=strlen(A+1)-1;
for(cod=0,i=1;i<=N;i++)
cod=cod*3+A[i]-'a';
Add(cod);
}
for(B=1,cod=0,i=1;i<=N;i++)
{
cod=cod*3+S[i]-'a';
if(i>1) B*=3;
}
Find(cod);
for(;i<=M;i++)
{
cod=cod-1LL*B*(S[i-N]-'a');
cod=cod*3+S[i]-'a';
Find(cod);
}
printf("%lld\n",sol);
return 0;
}