Pagini recente » Cod sursa (job #2002317) | Cod sursa (job #1217070) | Cod sursa (job #1040076) | RoadToIOI #4 | Cod sursa (job #2806952)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
#pragma GCC optimize("Ofast")
const int base = 3, mod = 666013;
int ans;
string s, cuv;
vector <unsigned int> dictionar[mod];
int len, s_len;
unsigned int base_pow;
bool check(unsigned int Hash)
{
unsigned int modh = Hash % mod;
for(int i = 0; i < (int) dictionar[modh].size(); i++)
if(Hash == dictionar[modh][i])
return true;
return false;
}
int main()
{
fin >> s;
s_len = s.size();
while(fin >> cuv)
{
len = cuv.size();
unsigned int myHash = 0;
for(int i = 0; i < len; i++)
myHash = myHash * base + (cuv[i] - 'a');
if(!check(myHash))
{
unsigned int modh = myHash % mod;
dictionar[modh].push_back(myHash);
}
}
base_pow = 1;
for(int i = 1; i < len; i++)
base_pow *= base;
unsigned int myHash = 0;
for(int i = 0; i < len; i++)
myHash = myHash * base + (s[i] - 'a');
if(check(myHash))
ans++;
for(int i = len; i < s_len; i++)
{
myHash = myHash - base_pow * (s[i - len] - 'a');
myHash = myHash * base + (s[i] - 'a');
if(check(myHash))
ans++;
}
fout << ans;
return 0;
}