Pagini recente » Cod sursa (job #56660) | Cod sursa (job #1308567) | Cod sursa (job #750595) | Cod sursa (job #2003499) | Cod sursa (job #2644876)
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int SIGMA = 26;
const int NMAX = 100;
const int WORDMAX = 10000;
const int TEXTMAX = 1000000;
struct Trie
{
Trie *sons[SIGMA];
Trie *failLink;
vector< int > wordlist;
int Count;
Trie()
{
failLink = NULL;
for(int i = 0; i < SIGMA; i++)
sons[i] = NULL;
Count = 0;
}
};
int N;
char Text[TEXTMAX + 5], Word[WORDMAX + 5];
Trie *Root = new Trie();
queue < Trie* > Q;
vector < Trie* > antibfs;
int freq[NMAX + 5];
void Insert(Trie *root, char *word, int wordId)
{
if(word[0] == '\0')
root->wordlist.push_back(wordId);
else
{
if(root->sons[word[0] - 'a'] == NULL)
root->sons[word[0] - 'a'] = new Trie();
Insert(root->sons[word[0] - 'a'], word + 1, wordId);
}
}
void computeAhoLinks()
{
Root->failLink = Root;
for(int i = 0; i < SIGMA; i++)
if(Root->sons[i] != NULL)
{
Root->sons[i]->failLink = Root;
Q.push(Root->sons[i]);
}
while(!Q.empty())
{
Trie *node = Q.front();
Q.pop();
for(int i = 0; i < SIGMA; i++)
{
if(node->sons[i] != NULL)
{
Trie *failNode = node->failLink;
while(failNode != Root && failNode->sons[i] == NULL)
failNode = failNode->failLink;
if(failNode->sons[i] != NULL && failNode->sons[i] != node->sons[i])
failNode = failNode->sons[i];
node->sons[i]->failLink = failNode;
Q.push(node->sons[i]);
}
}
}
}
void Solve(Trie *root, char *text)
{
Trie *node = root;
while(text[0] != '\0')
{
while(node != Root && node->sons[*text - 'a'] == NULL)
node = node->failLink;
if(node->sons[text[0] - 'a'] != NULL)
node = node->sons[text[0] - 'a'];
node->Count ++;
text++;
}
Q.push(root);
while(!Q.empty())
{
Trie *node = Q.front();
Q.pop();
antibfs.push_back(node);
for(int i = 0; i < SIGMA; i++)
if(node->sons[i] != NULL)
Q.push(node->sons[i]);
}
reverse(antibfs.begin(), antibfs.end());
for(auto node : antibfs)
{
for(auto wordId : node->wordlist)
freq[wordId] += node->Count;
if(node->failLink != NULL)
node->failLink->Count += node->Count;
}
for(int i = 1; i <= N; i++)
fout << freq[i] << '\n';
}
int main()
{
fin >> Text;
fin >> N;
for(int i = 1; i <= N; i++)
{
fin >> Word;
Insert(Root, Word, i);
}
computeAhoLinks();
Solve(Root, Text);
return 0;
}