Pagini recente » Cod sursa (job #2760128) | Cod sursa (job #2229266) | Cod sursa (job #1320012) | Cod sursa (job #1414256) | Cod sursa (job #3209100)
#include <bits/stdc++.h>
#define int unsigned int
#define DIM 1000001
#define BASE 666013
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
/*
char s[DIM], a[DIM], answer[DIM];
*/
string s, a, answer;
int power[DIM], _hash[DIM];
int ap[201], ap2[201 * 201];
int n, i, ret, new_hash, Max, Q;
vector <int> event[100001];
void build_hash(){
power[0] = 1;
for(i=1;i<=s.size();i++)
power[i] = (power[i - 1] * BASE);
_hash[2] = s[0];
for(i=2;i<=s.size();i++)
_hash[i + 1] = (_hash[i] * BASE + s[i - 1]);
}
int get_hash(int st, int dr){
int answer = (_hash[dr + 1] - _hash[st] * power[dr - st + 1]);
return answer;
}
int32_t main(){
fin >> s;
build_hash();
for(i=0;i<s.size() - 2;i++){
int aux = (s[i] * 4) + s[i + 1] * 2 + s[i + 2];
event[aux].push_back(i + 1);
ap[s[i]] += 1;
aux = s[i] * 100 + s[i + 1];
ap2[aux]++;
}
ap[s[s.size() - 1]]++;
ap[s[s.size() - 2]]++;
int aux = s[s.size() - 2] * 100 + s[s.size() - 1];
ap2[aux]++;
fin >> Q;
while(Q--){
fin >> a;
new_hash = 0;
ret = 0;
for(i=0;i<a.size();i++)
new_hash = (new_hash * BASE + a[i]);
if(a.size() == 1){
ret = ap[a[0]];
}
else if(a.size() == 2){
int aux = a[0] * 100 + a[1];
ret = ap2[aux];
}
else {
int aux = a[0] * 4 + a[1] * 2 + a[2];
for(auto k : event[aux]){
if(k + a.size() - 1 > s.size())
break;
if(get_hash(k, k + a.size() - 1) == new_hash){
++ret;
}
}
}
fout << ret << "\n";
}
}