Pagini recente » Cod sursa (job #434297) | Cod sursa (job #546609) | Cod sursa (job #608484) | Cod sursa (job #1407292) | Cod sursa (job #2871577)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
#define MOD1 1000000007
#define MOD2 1000000013
#define hash1 33
#define hash2 37
string A,B;
map <bool,map<int,int>> h;
long long sol,p1,p2,hashB1,hashA1,hashB2,hashA2,n,m;
int main()
{
fin>>A;
while(fin>>B)
{
m=B.size();
hashB1=hashB2=0;
for(int i=0; i<m; ++i)
{
hashB1=((hashB1*hash1)%MOD1+B[i])%MOD1;
hashB2=((hashB2*hash2)%MOD2+B[i])%MOD2;
}
h[hashB1][hashB2]=1;
}
p1=p2=1;
n=A.size();
for(int i=0; i<m; ++i)
{
hashA1=((hashA1*hash1)%MOD1+A[i])%MOD1;
hashA2=((hashA2*hash2)%MOD2+A[i])%MOD2;
if(i>0)
{
p1=(p1*hash1)%MOD1;
p2=(p2*hash2)%MOD2;
}
}
if(h[hashA1][hashA2]==1)sol++;
for(int i=m; i<n; ++i)
{
hashA1=((hash1*(hashA1-((A[i-m]*p1)%MOD1)+MOD1))%MOD1+A[i])%MOD1;
hashA2=((hash2*(hashA2-((A[i-m]*p2)%MOD2)+MOD2))%MOD2+A[i])%MOD2;
if(h[hashA1][hashA2]==1)sol++;
}
fout<<sol;
return 0;
}