Pagini recente » Cod sursa (job #2457595) | Cod sursa (job #1856108) | Cod sursa (job #1620664) | Cod sursa (job #1924042) | Cod sursa (job #2384226)
#include <bits/stdc++.h>
#define SIGMA 26
#define Nmax 105
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
string A,v[Nmax];
int ans[Nmax];
int N;
class Aho_corasick{
private:
struct node{
bitset <Nmax> pos_words;
node *fail_node=nullptr;
node *children[SIGMA];
node *parent=nullptr;
node(){
memset(children,0,sizeof(children));
pos_words.reset();
}
};
node *root=new node;
public:
void add(const string &s, const int &pos){
node *current_node=root;
for(const auto &it:s)
if(current_node->children[it-'a']){
current_node->children[it-'a']->parent=current_node;
current_node=current_node->children[it-'a'];
}
else{
current_node->children[it-'a']=new node;
current_node->children[it-'a']->parent=current_node;
current_node=current_node->children[it-'a'];
}
current_node->pos_words[pos]=true;
}
void add_fail_nodes(const int &N){
queue < pair <node*,node*> > q;
for(int i=0;i<SIGMA;i++)
if(root->children[i]){
root->children[i]->fail_node=root;
q.push({root,root->children[i]});
}
node *current_node,*fail_current_node;
while(!q.empty()){
current_node=q.front().second;
fail_current_node=q.front().first;
q.pop();
for(int i=0;i<SIGMA;i++)
if(current_node->children[i]){
bool found=false;
while(fail_current_node){
if(fail_current_node->children[i]){
current_node->children[i]->fail_node=fail_current_node->children[i];
found=true;
break;
}
else fail_current_node=fail_current_node->parent;
}
if(!found)
current_node->children[i]->fail_node=root;
for(int j=1;j<=N;j++)
current_node->children[i]->pos_words[j]=current_node->children[i]->pos_words[j]|current_node->children[i]->fail_node->pos_words[j];
q.push({current_node->children[i]->fail_node,current_node->children[i]});
}
}
}
void query(const string &s, const int &N){
node *current_node=root;
for(const auto &it:s){
while(current_node and !current_node->children[it-'a'])
current_node=current_node->fail_node;
if(!current_node)
current_node=root;
else{
current_node=current_node->children[it-'a'];
for(int i=1;i<=N;i++)
if(current_node->pos_words[i])
++ans[i];
}
}
}
};
int main(){
f>>A;
int N;
f>>N;
Aho_corasick T;
for(int i=1;i<=N;i++){
f>>v[i];
T.add(v[i],i);
}
T.add_fail_nodes(N);
T.query(A,N);
for(int i=1;i<=N;i++)
g<<ans[i]<<'\n';
return 0;
}