Pagini recente » Cod sursa (job #1977679) | Cod sursa (job #49895) | Cod sursa (job #395254) | Cod sursa (job #573927) | Cod sursa (job #2878634)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("abc2.in");
ofstream cout("abc2.out");
int base1=29,base2=31;
int mod1=66667,mod2=666013;
int HashA,HashB,HashC,HashD;
char str[10000001],a[21];
int power1,power2;
int lenghtA,lenghtstr;
int f1[66669],f2[666015];
int precalculate1()
{
power1=1;
for(int i=1;i<lenghtA;i++)
{
power1=(1LL*power1*base1)%mod1;
}
return power1;
}
int precalculate2()
{
power2=1;
for(int i=1;i<lenghtA;i++)
{
power2=(1LL*power2*base2)%mod2;
}
return power2;
}
int Create_HashA()
{
HashA=0;
for(int i=0;i<lenghtA;i++)
{
HashA=((1LL*HashA*base1)%mod1+a[i])%mod1;
}
return HashA;
}
int Create_HashC()
{
HashC=0;
for(int i=0;i<lenghtA;i++)
{
HashC=((1LL*HashC*base2)%mod2+a[i])%mod2;
}
return HashC;
}
int FindMatches()
{
long long cnt=0;
for(int i=0;i<lenghtA;i++)
{
HashB=((1LL*HashB*base1)%mod1+str[i])%mod1;
}
for(int i=0;i<lenghtA;i++)
{
HashD=((1LL*HashD*base2)%mod2+str[i])%mod2;
}
if(f1[HashB]!=0 and f2[HashD]!=0)
{
cnt++;
}
for(int i=lenghtA;i<lenghtstr;i++)
{
HashB=((HashB-str[i-lenghtA]*power1)%mod1+mod1)%mod1;
HashB=((1LL*HashB*base1)%mod1+str[i])%mod1;
HashD=((HashD-str[i-lenghtA]*power2)%mod2+mod2)%mod2;
HashD=((1LL*HashD*base2)%mod2+str[i])%mod2;
if(f1[HashB]!=0 and f2[HashD]!=0)
cnt++;
}
return cnt;
}
int main()
{
cin>>str;
lenghtstr=strlen(str);
cin>>a;
lenghtA=strlen(a);
precalculate1();
precalculate2();
int x=Create_HashA();
f1[x]=1;
int y=Create_HashC();
f2[y]=1;
while(cin>>a)
{
int x=Create_HashA();
f1[x]=1;
int y=Create_HashC();
f2[y]=1;
}
cout<<FindMatches();
return 0;
}