Pagini recente » Cod sursa (job #1824549) | Cod sursa (job #1725749) | Cod sursa (job #1525035) | Cod sursa (job #2076007) | Cod sursa (job #1757484)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int n;
char a[1000005], word[10005];
struct Trie {
int count;
Trie *sons[26], *back;
vector<Trie*> adj;
Trie() {
count = 0;
for (int i = 0; i < 26; ++i)
sons[i] = NULL;
back = NULL;
adj.clear();
}
} *root = new Trie, *res[105];
Trie *updateTrie(Trie *node, char *s) {
if (*s == 0)
return node;
if (node->sons[*s - 'a'] == NULL)
node->sons[*s - 'a'] = new Trie;
return updateTrie(node->sons[*s - 'a'], s + 1);
}
void bfs(void) {
queue<Trie*> que;
que.push(root);
while (!que.empty()) {
Trie *node = que.front();
for (int i = 0; i < 26; ++i) {
if (node->sons[i] == NULL)
continue;
Trie *aux = node->back;
while (aux && !aux->sons[i])
aux = aux->back;
if (!aux)
aux = root;
else
aux = aux->sons[i];
node->sons[i]->back = aux;
aux->adj.push_back(node->sons[i]);
que.push(node->sons[i]);
}
que.pop();
}
}
void dfs(Trie *node) {
for (vector<Trie*>::iterator adj = node->adj.begin(); adj != node->adj.end(); ++adj) {
dfs(*adj);
node->count += (*adj)->count;
}
}
int main() {
fin >> a;
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> word;
res[i] = updateTrie(root, word);
}
bfs();
Trie *curr = root;
for (char *pch = a; *pch; ++pch) {
while (curr && !curr->sons[*pch - 'a'])
curr = curr->back;
if (curr == NULL)
curr = root;
else
curr = curr->sons[*pch - 'a'];
curr->count++;
}
dfs(root);
for (int i = 1; i <= n; ++i)
fout << res[i]->count << '\n';
return 0;
}
//Trust me, I'm the Doctor!