Pagini recente » Cod sursa (job #1294708) | Cod sursa (job #1556249) | Cod sursa (job #1626114) | Cod sursa (job #2255426) | Cod sursa (job #3303163)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int NMAX = 100, SIGMA = 26;
int n, ans[NMAX];
string patterns[NMAX];
struct TrieNode
{
TrieNode *children[SIGMA], *fail_link;
vector<int> output;
TrieNode()
{
fill(children, children + SIGMA, nullptr);
fail_link = nullptr;
}
};
TrieNode *root = new TrieNode;
void adauga(const string &pattern, int idx)
{
TrieNode *node = root;
for(char ch : pattern)
{
if(node->children[ch - 'a'] == nullptr)
node->children[ch - 'a'] = new TrieNode;
node = node->children[ch - 'a'];
}
node->output.push_back(idx);
}
void build_fail_links()
{
queue<TrieNode*> q;
for(char ch = 'a'; ch <= 'z'; ch++)
{
if(root->children[ch - 'a'] != nullptr)
{
root->children[ch - 'a']->fail_link = root;
q.push(root->children[ch - 'a']);
}
}
while(!q.empty())
{
TrieNode *node = q.front();
q.pop();
for(char ch = 'a'; ch <= 'z'; ch++)
{
TrieNode *child = node->children[ch - 'a'];
if(child == nullptr)
continue;
TrieNode *fall_back = node->fail_link;
while(fall_back != nullptr && fall_back->children[ch - 'a'] == nullptr)
fall_back = fall_back->fail_link;
child->fail_link = (fall_back != nullptr ? fall_back->children[ch - 'a'] : root);
child->output.insert(child->output.end(), child->fail_link->output.begin(), child->fail_link->output.end());
q.push(child);
}
}
}
void cauta(const string &text)
{
TrieNode *node = root;
for(char ch : text)
{
while(node != nullptr && node->children[ch - 'a'] == nullptr)
node = node->fail_link;
node = (node != nullptr ? node->children[ch - 'a'] : root);
for(int idx : node->output)
ans[idx]++;
}
}
int main()
{
string text;
fin >> text >> n;
for(int i = 0; i < n; i++)
{
fin >> patterns[i];
adauga(patterns[i], i);
}
build_fail_links();
cauta(text);
for(int i = 0; i < n; i++)
fout << ans[i] << "\n";
fin.close();
fout.close();
return 0;
}