Pagini recente » Cod sursa (job #1694757) | Cod sursa (job #1788464) | Cod sursa (job #1038091) | Cod sursa (job #3290262) | Cod sursa (job #2723971)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct node {
node* to[26]; node* lps; int nr;
node() {memset(to, NULL, sizeof(to)); lps = NULL; nr = 0;}
node* go_to(char ch) { if(!to[ch - 'a']) return to[ch - 'a'] = new node(); return to[ch - 'a']; }
};
class Trie {
private:
vector <node*> t, nodes;
int k, n;
public:
node* root = new node();
void build(vector <string>& v) {
root -> lps = root; n = (int)v.size();
/// Building the dictionary
for(auto s : v) {
node* curr = root;
for(auto ch : s) curr = curr -> go_to(ch);
t.push_back(curr);
}
node* aux; nodes.push_back(root); k = 0;
/// BFS & getting lps for every node
while(k < (int)nodes.size()) {
node* top = nodes[k++];
for(short ch = 0; ch < 26; ch++) if(top -> to[ch]) {
for(aux = top -> lps; aux != root && !aux -> to[ch]; aux = aux -> lps);
if(aux -> to[ch] && aux != top) top -> to[ch] -> lps = aux -> to[ch];
else top -> to[ch] -> lps = root;
nodes.push_back(top -> to[ch]);
}
}
}
Trie() {}
Trie(vector <string>& v) {build(v);}
vector <int> get_occurences(string s) {
int len = s.length(); node* sn = root;
/// Traverse trie & add 1 at every node, return to lps while there's no route
for(int i = 0; i < len; i++) {
short ch = s[i] - 'a';
for(; sn != root && !sn -> to[ch]; sn = sn -> lps);
if(sn -> to[ch]) sn = sn -> to[ch];
sn -> nr++;
}
/// Add nr to nodes -> lps -> nr, the patterns recognized at lps(u), and only those,
/// are proper suffixes of L(u), and shall thus be recognized at state u as well
for(int i = k - 1; i >= 0; i--) nodes[i] -> lps -> nr += nodes[i] -> nr;
vector <int> res(n);
/// Set res for every word
for(int i = 0; i < n; i++) res[i] = t[i] -> nr;
return res;
}
};
string s;
vector <string> dict;
int n;
int main()
{
fin >> s;
fin >> n; dict.resize(n);
for(int i = 0; i < n; i++)
fin >> dict[i];
Trie T(dict);
vector <int> sol = T.get_occurences(s);
for(int i = 0; i < n; i++)
fout << sol[i] << "\n";
return 0;
}