Pagini recente » Cod sursa (job #2666408) | Cod sursa (job #3222416) | Cod sursa (job #2608505) | Cod sursa (job #2854950) | Cod sursa (job #3264809)
#include <bits/stdc++.h>
using namespace std;
#define INFILE "ahocorasick.in"
#define OUTFILE "ahocorasick.out"
const int LET_MAX = 26;
struct Node {
int out = 0;
vector<int> wordIndex;
Node *fail = nullptr;
Node *next[LET_MAX] = {};
};
stack<Node*> st;
void add(Node *root, string s, int index){
Node *current = root;
for(int i = 0; i < s.length(); ++i){
if(current -> next[s[i] - 'a'] == nullptr) current -> next[s[i] - 'a'] = new Node;
current = current -> next[s[i] - 'a'];
}
current -> wordIndex.push_back(index);
}
void ahoCorasick(Node *root){
queue<Node*> q;
q.push(root);
st.push(root);
while(!q.empty()){
Node *current = q.front(); q.pop();
for(int i = 'a'; i <= 'z'; ++i){
if(current -> next[i - 'a'] != nullptr){
q.push(current -> next[i - 'a']);
st.push(current -> next[i - 'a']);
Node *f = current -> fail;
while(f -> next[i - 'a'] == nullptr && f != root){
f = f -> fail;
}
if(f -> next[i - 'a'] != nullptr && f -> next[i - 'a'] != current -> next[i - 'a']){
f = f -> next[i - 'a'];
}
current -> next[i - 'a'] -> fail = f;
}
}
}
}
void revDfs(Node *root, vector<int> &ans){
while(!st.empty()){
Node *current = st.top(); st.pop();
if(current -> fail != nullptr) {
current -> fail -> out += current -> out;
}
for(int i = 0; i < current -> wordIndex.size(); ++i){
ans[current -> wordIndex[i]] = current -> out;
}
}
}
void solve(){
Node *root = new Node;
root -> fail = root;
string s; cin >> s;
int queries; cin >> queries;
vector<int> ans(queries, 0);
for(int i = 0; i < queries; ++i){
string aux; cin >> aux;
add(root, aux, i);
}
ahoCorasick(root);
Node *current = root;
for(int i = 0; i < s.length(); ++i){
while(current -> next[s[i] - 'a'] == nullptr && current != root) current = current -> fail;
if(current -> next[s[i] - 'a'] != nullptr) current = current -> next[s[i] - 'a'];
current -> out++;
}
revDfs(root, ans);
for(int i = 0; i < queries; ++i){
cout << ans[i] << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
freopen(INFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
solve();
return 0;
}