Pagini recente » Cod sursa (job #1763213) | Cod sursa (job #2337386) | Cod sursa (job #2089891) | Cod sursa (job #1858672) | Cod sursa (job #3036761)
#include <bits/stdc++.h>
using namespace std;
#define P 73
#define MOD1 100007
#define MOD2 100021
ifstream fin("abc2.in");
ofstream fout("abc2.out");
string t, s;
int P1, P2, slg, tlg, hashtable1[100007], hashtable2[100007];
int hash1(string s){
int hs=0;
for(int i=0; i<slg; i++){
hs = P*hs+s[i];
hs = hs%MOD1;
if(i) P1=(P1*P)%MOD1;
}
return hs;
}
int hash2(string s){
int hs=0;
for(int i=0; i<slg; i++){
hs = P*hs+s[i];
hs = hs%MOD2;
if(i) P2=(P2*P)%MOD2;
}
return hs;
}
int main(){
fin >> t;
tlg=t.length();
int ans=0, i=1;
while(fin >> s){
slg=s.length();
hashtable1[hash1(s)]=1;
hashtable2[hash2(s)]=1;
}
P1=P2=1;
int hs1=hash1(t.substr(0, slg));
int hs2=hash2(t.substr(0, slg));
ans+=(hashtable1[hs1] && hashtable2[hs2]);
for(int i=slg; i<tlg; i++){
hs1 = ((hs1 - (t[i - slg] * P1) % MOD1 + MOD1) * P + t[i]) % MOD1;
hs2 = ((hs2 - (t[i - slg] * P2) % MOD2 + MOD2) * P + t[i]) % MOD2;
ans+=(hashtable1[hs1] && hashtable2[hs2]);
}
fout << ans;
}