Pagini recente » Cod sursa (job #612859) | Cod sursa (job #2750926) | Cod sursa (job #3257324) | Cod sursa (job #2100365) | Cod sursa (job #2382300)
#include <bits/stdc++.h>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int MAX_LEN = 20000001,
MOD = 1e9 + 9,
EXP = 31;
bool E[MOD];
int preComp[21],
wordSize, cnt;
string S, tmp;
int compHash(const string& s) {
int hashVal = 0;
for(int i = 0; i < s.size(); i++)
hashVal = (1ULL * hashVal + 1ULL * (s[i] - 'a' + 1) * preComp[i]) % MOD;
return hashVal;
}
void match() {
for(int i = 0, j = S.size()-wordSize; i < j; i++)
if(E[compHash(S.substr(i, wordSize))])
cnt++;
}
int main()
{
S.reserve(MAX_LEN);
preComp[0] = 1;
for(int i = 1; i <= 20; i++)
preComp[i] = (1ULL * preComp[i-1] * EXP) % MOD;
in >> S;
in >> tmp;
E[compHash(tmp)] = 1;
wordSize = tmp.size();
while(in >> tmp)
E[compHash(tmp)] = 1;
match();
out << cnt << '\n';
return 0;
}