Pagini recente » Borderou de evaluare (job #3365629) | Borderou de evaluare (job #3366598) | Borderou de evaluare (job #3365630) | Cod sursa (job #3365629) | Cod sursa (job #3366598)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int SIGMA = 26, QUERIES = 2e5;
int ans[QUERIES];
class AhoCorasick
{
private:
struct Node
{
Node *children[SIGMA], *link;
int used = 0;
vector<int> ending;
Node()
{
fill(children, children + SIGMA, nullptr);
}
};
Node *root = new Node;
vector<Node*> order;
public:
void adauga(const string &word, int id)
{
Node *node = root;
for(char ch : word)
{
if(node->children[ch - 'a'] == nullptr)
node->children[ch - 'a'] = new Node;
node = node->children[ch - 'a'];
}
node->ending.push_back(id);
}
void precalculare()
{
queue<Node*> Q({root});
root->link = root;
while(!Q.empty())
{
Node *node = Q.front(); Q.pop();
order.push_back(node);
for(int ch = 0; ch < SIGMA; ch++)
{
Node *child = node->children[ch];
if(child == nullptr)
continue;
Node *fall = node->link;
while(fall != root && fall->children[ch] == nullptr)
fall = fall->link;
if(fall->children[ch] != nullptr && fall->children[ch] != child)
child->link = fall->children[ch];
else
child->link = root;
Q.push(child);
}
}
}
void cauta(const string &text)
{
Node *node = root;
for(char ch : text)
{
while(node != root && node->children[ch - 'a'] == nullptr)
node = node->link;
if(node->children[ch - 'a'] != nullptr)
node = node->children[ch - 'a'];
node->used++;
}
reverse(order.begin(), order.end());
for(auto node : order)
{
for(int id : node->ending)
ans[id] += node->used;
node->link->used += node->used;
}
}
};
int main()
{
int q;
string text;
fin >> text >> q;
AhoCorasick aho;
for(int i = 0; i < q; i++)
{
string word;
fin >> word;
aho.adauga(word, i);
}
aho.precalculare();
aho.cauta(text);
for(int i = 0; i < q; i++)
fout << ans[i] << "\n";
return 0;
}