Pagini recente » Cod sursa (job #3002140) | Cod sursa (job #634481) | Cod sursa (job #3031193) | Cod sursa (job #540688) | Cod sursa (job #2167111)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 5;
const int MOD1 = 1e9 + 7;
const int BASE1 = 71;
const int MOD2 = 1e9 + 9;
const int BASE2 = 101;
char A[N];
char buffer[N];
pair<int, int> queryHash[105];
int sz[105];
pair <int, int> h[N];
pair <int, int> inv[N];
int lgpow(int b, int e, int m){
int sol = 1;
while(e){
if(e & 1){
sol = (1LL * sol * b)%m;
}
b = (1LL * b * b)%m;
e >>= 1;
}
return sol;
}
struct Hash{
pair <int, int> getHash(char *s){
int n = strlen(s + 1);
pair <int, int> ret = {0, 0};
int p1 = 1;
int p2 = 1;
for(int i = 1;i <= n;i++){
ret.first = (0LL + ret.first + 1LL * p1 * (s[i] - 'a' + 1))%MOD1;
ret.second = (0LL + ret.second + 1LL * p2 * (s[i] - 'a' + 1))%MOD2;
p1 = (1LL * p1 * BASE1)%MOD1;
p2 = (1LL * p2 * BASE2)%MOD2;
}
return ret;
}
};
pair <int, int> getSubHash(int i, int l){
pair <int, int> ret = {(h[i].first - h[i - l].first + MOD1)%MOD1, (h[i].second - h[i - l].second + MOD2)%MOD2};
ret.first = (1LL * ret.first * inv[i - l].first)%MOD1;
ret.second = (1LL * ret.second * inv[i - l].second)%MOD2;
return ret;
}
vector <pair<int, int>> hashes[10005];
vector <int> toSearch;
bool usedL[10005];
int main(){
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
Hash HashClass;
scanf("%s", A + 1);
int l = strlen(A + 1);
int IB1 = lgpow(BASE1, MOD1 - 2, MOD1);
int IB2 = lgpow(BASE2, MOD2 - 2, MOD2);
inv[0] = {1, 1};
int p1, p2;
p1 = p2 = 1;
for(int i = 1;i <= l;i++){
inv[i].first = (1LL * inv[i - 1].first * IB1)%MOD1;
inv[i].second = (1LL * inv[i - 1].second * IB2)%MOD2;
h[i].first = (0LL + h[i - 1].first + 1LL * p1 * (A[i] - 'a' + 1))%MOD1;
h[i].second = (0LL + h[i - 1].second + 1LL * p2 * (A[i] - 'a' + 1))%MOD2;
p1 = (1LL * p1 * BASE1)%MOD1;
p2 = (1LL * p2 * BASE2)%MOD2;
}
int n;
scanf("%d", &n);
for(int i = 1;i <= n;i++){
scanf("%s", buffer + 1);
queryHash[i] = HashClass.getHash(buffer);
sz[i] = strlen(buffer + 1);
if(usedL[sz[i]] == false)
toSearch.emplace_back(sz[i]);
usedL[sz[i]] = true;
}
for(auto &it : toSearch){
for(int i = it;i <= l;i++){
hashes[it].emplace_back(getSubHash(i, it));
}
sort(hashes[it].begin(), hashes[it].end());
}
for(int i = 1;i <= n;i++){
printf("%d\n", upper_bound(hashes[sz[i]].begin(), hashes[sz[i]].end(), queryHash[i]) - lower_bound(hashes[sz[i]].begin(), hashes[sz[i]].end(), queryHash[i]));
}
return 0;
}