Pagini recente » Cod sursa (job #1308480) | Cod sursa (job #2109346) | Cod sursa (job #152409) | Cod sursa (job #2203548) | Cod sursa (job #2811752)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
#pragma GCC optimize("Ofast")
const int base = 3, mod = 30007;
int ans;
string s, t;
vector <unsigned int> d[mod];
int len, len_t;
unsigned int base_pow = 1;
bool check(unsigned int Hash)
{
unsigned int modh = Hash % mod;
for(int i = 0; i < d[modh].size(); i++)
if(d[modh][i] == Hash)
return true;
return false;
}
void adauga(string s)
{
unsigned int myHash = 0;
for (int i = 0; i < len_t; i++)
myHash = myHash * base + (s[i] - 'a');
if (!check(myHash)) {
unsigned int hmod = myHash % mod;
d[hmod].push_back(myHash);
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin >> s;
len = s.length();
while(fin >> t)
{
len_t = t.length();
adauga(t);
}
for(int i = 1; i < len_t; i++)
base_pow = base_pow * base;
unsigned int myHash = 0;
for(int i = 0; i < len_t; i++)
myHash = myHash * base + (s[i] - 'a');
if(check(myHash))
ans++;
for(int i = len_t; i < len; i++) {
int prev_val = s[i - len_t] - 'a', val = s[i] - 'a';
myHash = (myHash - (prev_val * base_pow)) * base + val;
if(check(myHash))
ans++;
}
fout << ans;
return 0;
}