Pagini recente » Cod sursa (job #344135) | Cod sursa (job #537644) | Cod sursa (job #1142460) | Cod sursa (job #2550039) | Cod sursa (job #2606208)
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int NMAX = 105;
const int LMAX = 26;
struct node {
vector<int> endInNode;
node* next[LMAX];
node* link;
int cntText;
node() {
fill(begin(next), end(next), nullptr);
link = nullptr;
}
};
node* root = new node();
string text;
int N, ans[NMAX];
string words[NMAX];
vector<node*> sortedNodes;
void insertWord(node* currNode, string& word, int idx) {
for (size_t idx = 0; idx < word.size(); idx++) {
int chIdx = word[idx] - 'a';
if (currNode -> next[chIdx] == NULL) {
currNode -> next[chIdx] = new node();
}
currNode = currNode -> next[chIdx];
}
currNode -> endInNode.push_back(idx);
}
void bfsAndComputeSuffixLink() {
root -> link = root;
queue<node*> nodes;
nodes.push(root);
while (!nodes.empty()) {
node* currNode = nodes.front();
nodes.pop();
sortedNodes.push_back(currNode);
for (int idx = 0; idx < LMAX; idx++) {
if (currNode -> next[idx] != NULL) {
nodes.push(currNode -> next[idx]);
node* nextNode = currNode -> next[idx];
if (currNode == root) {
nextNode -> link = root;
} else {
node* suffixLink = currNode -> link;
while (suffixLink != root && suffixLink -> next[idx] == NULL) {
suffixLink = suffixLink -> link;
}
nextNode -> link = (suffixLink -> next[idx] != NULL) ? suffixLink -> next[idx] : root;
}
}
}
}
}
void processText(string& text) {
node* currNode = root;
for (size_t idx = 0; idx < text.size(); idx++) {
int chIdx = text[idx] - 'a';
while (currNode != root && currNode -> next[chIdx] == NULL) {
currNode = currNode -> link;
}
currNode = (currNode -> next[chIdx] != NULL) ? currNode -> next[chIdx] : root;
currNode -> cntText++;
}
}
void ansQueries() {
for (auto it = sortedNodes.rbegin(); it != sortedNodes.rend(); it++) {
node* currNode = *it;
(currNode -> link) -> cntText += currNode -> cntText;
for (auto wordIdx : currNode -> endInNode) {
ans[wordIdx] = currNode -> cntText;
}
}
for (int idx = 0; idx < N; idx++) {
cout << ans[idx] << "\n";
}
}
int main() {
freopen("ahocorrasick.in", "r", stdin);
freopen("ahocorrasick.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> text;
cin >> N;
for (int idx = 0; idx < N; idx++) {
cin >> words[idx];
insertWord(root, words[idx], idx);
}
bfsAndComputeSuffixLink();
processText(text);
ansQueries();
return 0;
}