Pagini recente » Cod sursa (job #2384988) | Cod sursa (job #2679623) | Cod sursa (job #2675977) | Cod sursa (job #2424008) | Cod sursa (job #2685911)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
struct TrieNode
{
TrieNode *next[26];
TrieNode *suf;
int fv;
TrieNode()
{
this->fv=0;
this->suf=NULL;
memset(this->next,0,sizeof(this->next));
}
};
TrieNode *root = new TrieNode();
TrieNode* ans[1000005];
void insert(TrieNode *node,string &s,const int index,int i,const int len)
{
if(i==len)
{
ans[index]=node;
return;
}
int aux=s[i]-'a';
if(node->next[aux]==nullptr)
node->next[aux]=new TrieNode();
insert(node->next[aux],s,index,i+1,len);
}
vector<TrieNode*> fin;
void linking()
{
queue <TrieNode*> q;
q.push(root);
while(!q.empty())
{
TrieNode *nod=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(nod->next[i]!=nullptr)
{
TrieNode *current;
TrieNode *sufix;
current=nod->next[i];
sufix=nod->suf;
fin.push_back(current);
while(sufix!=root && sufix->next[i]==nullptr)
sufix=sufix->suf;
if(sufix->next[i]!=nullptr && sufix->next[i]!=current)
current->suf=sufix->next[i];
else
current->suf=root;
q.push(current);
}
}
}
}
int main()
{
string s;
in>>s;
int n;
in>>n;
for(int i=1;i<=n;i++)
{
string ss;
in>>ss;
int lung=ss.length();
insert(root,ss,i,0,lung);
}
linking();
TrieNode *aux = root;
for(auto ch:s)
{
int next_ch=ch-'a';
while(aux!=root && aux->next[next_ch]==nullptr)
aux=aux->suf;
if(aux->next[next_ch]!=nullptr)
{
aux=aux->next[next_ch];
aux->fv ++;
}
}
for(int i=fin.size()-1;i>=0;i--)
fin[i]-> suf-> fv+=fin[i]-> fv;
for(int i=1;i<=n;i++)
out<<ans[i]->fv<<"\n";
return 0;
}