Pagini recente » Istoria paginii utilizator/1475369147896537415369 | Cod sursa (job #1018559) | Cod sursa (job #2613021) | Cod sursa (job #293002) | Cod sursa (job #2187483)
#include <bits/stdc++.h>
using namespace std;
ifstream fi( "ahocorasick.in" ); ofstream fo( "ahocorasick.out" );
const int maxn = 1e6 + 5;
const int maxl = 1e4 + 5;
const int maxw = 105;
const int sigma = 26;
struct trie {
int match;
trie *son[sigma], *fail;
vector <int> pos;
trie() {
memset(son, 0, sizeof son);
fail = 0;
match = 0;
pos.clear();
}
} *root;
char s[maxn], word[maxl];
int n, length, ans[maxw], l, r;
void tinsert(trie *node, char *str, int idx) {
if (*str == 0) {
node->pos.push_back(idx);
return;
}
if (node->son[*str - 'a'] == NULL)
node->son[*str - 'a'] = new trie();
tinsert(node->son[*str - 'a'], str + 1, idx);
}
trie* q[maxn];
void bfs() {
trie *node, *aux;
l = r = 0;
root->fail = root;
q[r++] = root;
while (l < r) {
node = q[l++];
for (int i = 0; i < sigma; i++) {
if (node->son[ i ] == NULL)
continue;
aux = node->fail;
while (aux != root && aux->son[ i ] == NULL)
aux = aux->fail;
if (aux->son[ i ] != NULL && aux->son[ i ] != node->son[ i ])
aux = aux->son[ i ];
node->son[ i ]->fail = aux;
q[r++] = node->son[ i ];
}
}
root->fail = NULL;
}
void solve() {
length = strlen(s);
trie *aux = root;
for (int i = 0; i < length; i++) {
while (aux != NULL && aux->son[s[ i ] - 'a'] == NULL && aux != root)
aux = aux->fail;
if (aux->son[s[ i ] - 'a'] != NULL)
aux = aux->son[s[ i ] - 'a'];
aux->match++;
}
}
void antibfs() {
trie *node;
for (int i = r - 1; i >= 0; i--) {
node = q[ i ];
if (node->fail != NULL)
node->fail->match += node->match;
for (int idx: node->pos)
ans[ idx ] = node->match;
}
}
int main()
{
fi >> s >> n;
root = new trie();
for (int i = 1; i <= n; i++) {
fi >> word;
tinsert(root, word, i);
}
bfs();
solve();
antibfs();
for (int i = 1; i <= n; i++)
fo << ans[ i ] << "\n";
fo.close();
fi.close();
return 0;
}