Pagini recente » Cod sursa (job #77423) | Monitorul de evaluare | Cod sursa (job #177907) | Cod sursa (job #264193) | Cod sursa (job #3307334)
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
class Node {
public:
vector<Node*> kids;
Node* suffixLink;
int cnt;
Node(int alphaSize) {
kids.resize(alphaSize, NULL);
suffixLink = NULL;
cnt = 0;
}
};
class AhoCorasick {
public:
Node* root;
int alphaSize;
AhoCorasick(int size) {
alphaSize = size;
root = new Node(size);
}
bool checkChild(Node* node, int childId) {
return (node->kids[childId] != NULL);
}
void addChild(Node* node, int childId) {
node->kids[childId] = new Node(alphaSize);
}
Node* insert(string s) {
Node* node = root;
for (char ch: s) {
int childId = int(ch - 'a');
if (!checkChild(node, childId)) {
addChild(node, childId);
}
node = node->kids[childId];
}
return node;
}
void solvePrefix(Node* node, int childId) {
Node* pref = node->suffixLink;
while (pref != root && !pref->kids[childId]) {
pref = pref->suffixLink;
}
if(pref->kids[childId] && pref->kids[childId] != node->kids[childId]) {
node->kids[childId]->suffixLink = pref->kids[childId];
} else {
node->kids[childId]->suffixLink = root;
}
}
void build() {
root->suffixLink = root;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
for (int i = 0; i < alphaSize; i++) {
if (node->kids[i]) {
solvePrefix(node, i);
q.push(node->kids[i]);
}
}
}
}
void solve(string s) {
Node* node = root;
for (char ch: s) {
int childId = int(ch - 'a');
while(node != root && !node->kids[childId]) {
node = node->suffixLink;
}
if (node->kids[childId]) {
node = node->kids[childId];
}
node->cnt++;
}
vector<Node*> bfsOrder;
bfsOrder.push_back(root);
for (int i = 0; i < int(bfsOrder.size()); i++) {
Node* node = bfsOrder[i];
for (int j = 0; j < alphaSize; j++) {
if (node->kids[j]) {
bfsOrder.push_back(node->kids[j]);
}
}
}
for (int i = bfsOrder.size() - 1; i >= 0; i--) {
Node* node = bfsOrder[i];
node->suffixLink->cnt += node->cnt;
}
}
};
int main() {
int n;
string text;
cin >> text >> n;
AhoCorasick automaton(26);
vector <Node*> termNodes(n, NULL);
for (int i = 0; i < n; i++) {
string pattern;
cin >> pattern;
termNodes[i] = automaton.insert(pattern);
}
automaton.build();
automaton.solve(text);
for (int i = 0; i < n; i++) {
cout << termNodes[i]->cnt << '\n';
}
}