Pagini recente » Cod sursa (job #2296445) | Cod sursa (job #645412) | Cod sursa (job #2375680) | Rating Sabin Anton (sabinanton) | Cod sursa (job #2357720)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream in ("ahocorasick.in");
ofstream out ("ahocorasick.out");
#define ll long long
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 100;
int const sigma = 26;
struct Trie{
int val;
int scount;
Trie* son[sigma];
Trie* failure;
Trie(){
val = scount = 0;
for(int i = 0; i < sigma; i++)
son[i] = nullptr;
failure = nullptr;
}
};
Trie* root;
void addtrie(Trie* &node, string &s, int pos, int code){
if(pos == s.size()) {
node->val = code;
return ;
} else {
if(node->son[s[pos] - 'a'] == nullptr)
node->son[s[pos] - 'a'] = new Trie();
addtrie(node->son[s[pos] - 'a'], s, pos + 1, code);
}
}
void addFailure(Trie* &node, int ch ){
if(node->son[ch] == nullptr)
return ;
else {
Trie* &newnode = node->son[ch];
if(node == root) {
newnode->failure = root;
return ;
}
if(newnode->failure == nullptr){
newnode->failure = node->failure;
while(root != newnode->failure && newnode->failure->son[ch] == nullptr)
newnode->failure = newnode->failure->failure;
if(newnode->failure->son[ch] == nullptr)
newnode->failure = root;
else
newnode->failure = newnode->failure->son[ch];
}
}
}
void explore(Trie* &node, char ch){
while(root != node && node->son[ch - 'a'] == nullptr)
node = node->failure;
if(node->son[ch - 'a'] != nullptr)
node = node->son[ch - 'a'];
else
node = root;
}
string s[5 + nmax];
bool compare(int x,int y){
return s[x].size() < s[y].size();
}
int sol[5 + nmax];
vector<Trie*> order;
void bfs(Trie* node){
queue<Trie*> q;
q.push(node);
order.push_back(node);
while(0 < q.size()){
node = q.front();
q.pop();
for(int h = 0; h < sigma; h++)
if(node->son[h] != nullptr){
q.push({node->son[h]});
order.push_back(node->son[h]);
}
}
}
string printsequence;
int main()
{
root = new Trie();
root->failure = root;
string original;
int n;
in >> original >> n;
for(int i = 1;i <= n; i++)
in >> s[i];
for(int i = 1; i <= n; i++)
addtrie(root, s[i], 0, i);
bfs(root);
for(int i = 0;i < order.size(); i++)
for(int h = 0; h < sigma; h++)
if(order[i]->son[h] != nullptr)
addFailure(order[i], h);
Trie* currentpos = root;
for(int i = 0; i < original.size(); i++) {
explore(currentpos, original[i]);
currentpos->scount++;
}
for(int i = order.size() - 1;0 < i;i--){
order[i]->failure->scount += order[i]->scount;
sol[order[i]->val] = order[i]->scount;
}
for(int i = 1;i <= n;i++)
out << sol[i] << '\n';
return 0;
}