Pagini recente » Cod sursa (job #464587) | Cod sursa (job #3303752)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
const int lg=26;
struct trie
{
trie *children[lg];
trie *fall;
int cnt;
trie()
{
cnt=0;
fall=NULL;
for (int i=0; i<lg; i++)
children[i]=NULL;
}
};
trie *root, *out[105];
queue <trie*> q;
void insert_word (trie *root, string word, int ind)
{
trie *curr=root;
for (auto c:word)
{
int key=c-'a';
if (curr->children[key]==NULL)
curr->children[key]=new trie();
curr=curr->children[key];
}
out[ind]=curr;
}
string s;
void corasick ()
{
vector <trie*> ord;
root->fall=root;
q.push(root);
while (!q.empty())
{
trie *node=q.front();
q.pop();
ord.push_back(node);
for (int i=0; i<lg; i++)
{
if (node->children[i]==NULL)
continue;
trie *suf=node->fall;
while (suf!=root && suf->children[i]==NULL)
suf=suf->fall;
if (suf->children[i]!=NULL && suf->children[i]!=node->children[i])
node->children[i]->fall=suf->children[i];
else
node->children[i]->fall=root;
q.push(node->children[i]);
}
}
trie *node=root;
for (int i=0; i<s.size(); i++)
{
int key=s[i]-'a';
while (node!=root && node->children[key]==NULL)
node=node->fall;
if (node->children[key]!=NULL)
node=node->children[key];
node->cnt++;
}
for (int i=ord.size()-1; i>=0; i--)
ord[i]->fall->cnt+=ord[i]->cnt;
}
int main()
{
root=new trie();
fin >> s;
int n;
fin >> n;
for (int i=1; i<=n; i++)
{
string t;
fin >> t;
insert_word(root,t,i);
}
corasick();
for (int i=1; i<=n; i++)
fout << out[i]->cnt << '\n';
return 0;
}