Pagini recente » Cod sursa (job #269647) | Cod sursa (job #1446059) | Cod sursa (job #1014321) | Cod sursa (job #297167) | Cod sursa (job #2606226)
#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;
int next[LMAX];
int link;
int cntText;
node() {
fill(begin(next), end(next), -1);
link = -1;
cntText = 0;
}
};
vector<node> nodesList(1);
const int ROOT = 0;
string text;
int N, ans[NMAX];
string words[NMAX];
vector<int> sortedNodes;
void insertWord(int currNode, string& word, int idx) {
for (size_t idx = 0; idx < word.size(); idx++) {
int chIdx = word[idx] - 'a';
if (nodesList[currNode].next[chIdx] == -1) {
nodesList[currNode].next[chIdx] = nodesList.size();
nodesList.emplace_back();
}
currNode = nodesList[currNode].next[chIdx];
}
nodesList[currNode].endInNode.push_back(idx);
}
void bfsAndComputeSuffixLink() {
nodesList[ROOT].link = ROOT;
queue<int> nodes;
nodes.push(ROOT);
while (!nodes.empty()) {
int currNode = nodes.front();
nodes.pop();
sortedNodes.push_back(currNode);
for (int idx = 0; idx < LMAX; idx++) {
if (nodesList[currNode].next[idx] != -1) {
int nextNode = nodesList[currNode].next[idx];
nodes.push(nextNode);
if (currNode == ROOT) {
nodesList[nextNode].link = ROOT;
} else {
int suffixLink = nodesList[currNode].link;
while (suffixLink != ROOT && nodesList[suffixLink].next[idx] == -1) {
suffixLink = nodesList[suffixLink].link;
}
nodesList[nextNode].link = nodesList[suffixLink].next[idx] != -1 ? nodesList[suffixLink].next[idx] : ROOT;
}
}
}
}
}
void processText(string& text) {
int currNode = ROOT;
for (size_t idx = 0; idx < text.size(); idx++) {
int chIdx = text[idx] - 'a';
while (currNode != ROOT && nodesList[currNode].next[chIdx] == -1) {
currNode = nodesList[currNode].link;
}
currNode = (nodesList[currNode].next[chIdx] != -1) ? nodesList[currNode].next[chIdx] : ROOT;
nodesList[currNode].cntText++;
}
}
void ansQueries() {
for (auto it = sortedNodes.rbegin(); it != sortedNodes.rend(); it++) {
int currNode = *it;
nodesList[nodesList[currNode].link].cntText += nodesList[currNode].cntText;
for (auto wordIdx : nodesList[currNode].endInNode) {
ans[wordIdx] = nodesList[currNode].cntText;
}
}
for (int idx = 0; idx < N; idx++) {
cout << ans[idx] << "\n";
}
}
int main() {
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.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;
}