Pagini recente » Cod sursa (job #3238174) | Cod sursa (job #1312195) | Cod sursa (job #2187885) | Cod sursa (job #92161) | Cod sursa (job #3250408)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
struct Node
{
int out = 0;
vector<int> wordIndex;
Node *fail = nullptr;
Node *next[26] = {};
};
stack<Node*> Stack;
void add(Node *root, string str, int index)
{
Node *current = root;
for(int i = 0; i < str.size(); i++){
if(current->next[str[i]-'a'] == nullptr){
current->next[str[i]-'a'] = new Node;
}
current = current->next[str[i]-'a'];
}
current->wordIndex.push_back(index);
}
void Aho_Corasick(Node *root)
{
queue<Node*> queue;
queue.push(root);
Stack.push(root);
while(!queue.empty()){
Node *current = queue.front();
queue.pop();
for(int i = 'a'; i <= 'z'; i++){
if(current->next[i-'a'] != nullptr){
queue.push(current->next[i-'a']);
Stack.push(current->next[i-'a']);
Node *f = current->fail;
while(f->next[i-'a'] == nullptr && f != root){
f = f->fail;
}
if(f->next[i-'a'] != nullptr && f->next[i-'a'] != current->next[i-'a']){
f = f->next[i-'a'];
}
current->next[i-'a']->fail = f;
}
}
}
}
void InverseBFS(Node *root, vector<int> &solution)
{
while(!Stack.empty()){
Node *current = Stack.top();
Stack.pop();
if(current->fail != nullptr){
current->fail->out += current->out;
}
for(int i = 0; i < current->wordIndex.size(); i++){
solution[current->wordIndex[i]] = current->out;
}
}
}
int main()
{
Node *root = new Node;
root->fail = root;
int n;
string A;
in >> A >> n;
vector<int> solution(n, 0);
for(int i = 0; i < n; i++){
string temp;
in >> temp;
add(root, temp, i);
}
Aho_Corasick(root);
Node *current = root;
for(int i = 0; i < A.size(); i++){
while(current->next[A[i]-'a'] == nullptr && current != root){
current = current->fail;
}
if(current->next[A[i]-'a'] != nullptr){
current = current->next[A[i]-'a'];
}
current->out++;
}
InverseBFS(root, solution);
for(int i = 0; i < n; i++){
out << solution[i] << endl;
}
return 0;
}