Pagini recente » Cod sursa (job #946286) | Cod sursa (job #3269392) | Cod sursa (job #3004731) | Cod sursa (job #1032795) | Cod sursa (job #2931627)
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
int n;
char str[N], cuv[10005];
int result[101];
int st, fn;
struct Trie {
int number;
vector<int> indices;
Trie* children[26];
Trie* fail;
Trie() {
number = 0;
memset(children, 0, sizeof(children));
fail = NULL;
}
};
Trie *U = new Trie, *T = new Trie;
Trie* q[10000 * 10000 + 5];
void insert(Trie* node, char* word, int ind) {
if(!isalpha(*word)) {
node->indices.push_back(ind);
return;
}
int next = *word - 'a';
if(!(node->children[next])) {
node->children[next] = new Trie;
}
insert(node->children[next], word + 1, ind);
}
void read() {
f>>str;
f>>n;
for(int i = 1;i <= n;++i) {
f>>cuv;
insert(T, cuv, i);
}
}
void precompute() {
Trie *top, *fa;
T->fail = T;
for(q[st = fn = 1] = T;st <= fn;++st) {
top = q[st];
for(int next = 0;next < 26;++next) {
if(top->children[next]) {
for(fa = top->fail;fa != T && !(fa->children[next]);fa = fa->fail);
if(fa->children[next] && fa->children[next] != top->children[next]) {
fa = fa->children[next];
}
top->children[next]->fail = fa;
q[++fn] = top->children[next];
}
}
}
}
void compute() {
Trie* top;
for(int ind = fn;ind >= 1;--ind) {
top = q[ind];
if(top->fail) {
top->fail->number += top->number;
}
for(const auto& index : top->indices) {
result[index] += top->number;
}
}
}
void solve() {
precompute();
U = T;
int len = strlen(str);
for(int i = 0;i < len;++i) {
int next = str[i] - 'a';
while(U != T && !(U->children[next])) {
U = U->fail;
}
if(U->children[next]) {
U = U->children[next];
}
U->number++;
}
compute();
for(int i = 1;i <= n;++i) {
g<<result[i]<<'\n';
}
}
int main() {
read();
solve();
return 0;
}