Pagini recente » Cod sursa (job #2732859) | Cod sursa (job #2162417) | Cod sursa (job #2269390) | Cod sursa (job #1093093)
#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<pair<ll,int> > V[MOD];
vector<pair<ll,int> >::iterator it;
void Add(long long x)
{
r=x%MOD;
for(it=V[r].begin();it!=V[r].end();it++)
if(it->first==x) {it->second++; return;}
V[r].push_back(make_pair(x,1));
}
int Find(long long x)
{
r=x%MOD;
for(it=V[r].begin();it!=V[r].end();it++)
if(it->first==x)
{
int c=it->second;
it->second=0;
return c;
}
return 0;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(S+1,NMAX,stdin);
fgets(A+1,DMAX,stdin);
N=strlen(A+1)-1;
M=strlen(S+1)-1;
for(B=1,i=1;i<=N;i++)
{
cod=cod*3+S[i]-'a';
if(i>1) B*=3;
}
Add(cod);
for(;i<=M;i++)
{
cod=cod-1LL*B*(S[i-N]-'a');
cod=cod*3+S[i]-'a';
Add(cod);
}
for(cod=0,i=1;i<=N;i++)
cod=cod*3+A[i]-'a';
sol+=Find(cod);
while(fgets(A+1,DMAX,stdin))
{
for(cod=0,i=1;i<=N;i++)
cod=cod*3+A[i]-'a';
sol+=Find(cod);
}
printf("%lld\n",sol);
return 0;
}