Pagini recente » Cod sursa (job #1758327) | Cod sursa (job #2006796) | Cod sursa (job #2548425) | Cod sursa (job #717697) | Cod sursa (job #3036755)
#include <bits/stdc++.h>
using namespace std;
#define P 73
#define MOD1 100007
#define MOD2 100021
ifstream fin("abc2.in");
ofstream fout("abc2.out");
unordered_map<string, pair<int, int>> mp;
string t, s;
int P1, P2, slg, tlg;
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();
if(mp[s]==make_pair(0, 0)) mp[s]={hash1(s), hash2(s)};
}
P1=P2=1;
int hs1=hash1(t.substr(0, slg));
int hs2=hash2(t.substr(0, slg));
for(auto u : mp) if(u.second.first==hs1 && u.second.second==hs2) ans++;
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;
for(auto u : mp) if(u.second.first==hs1 && u.second.second==hs2) ans++;
}
fout << ans;
}