fork download
copy 
  1. /*
  2.   Copyright 2013 Marek "p2004a" Rusinowski
  3.   Aho-Corasick algorithm
  4. */
  5. #include <cstdio>
  6. #include <vector>
  7. #include <string>
  8. #include <deque>
  9.  
  10. #define MAXN 1000000
  11.  
  12. using namespace std;
  13.  
  14. class PatternsMatcher {
  15.   class TrieNode {
  16.    public:
  17.     static int it;
  18.     TrieNode *son[26];
  19.     int num;
  20.     TrieNode *fail;
  21.  
  22.     TrieNode() : num(0), fail(NULL) {
  23.       for (int i = 0; i < 26; ++i) son[i] = NULL;
  24.     }
  25.  
  26.     TrieNode(const char *str) : num(0), fail(NULL) {
  27.       for (int i = 0; i < 26; ++i) son[i] = NULL;
  28.       if (*str != '\0') son[*str - 'a'] = new TrieNode(str + 1);
  29.       else num = ++it;
  30.     }
  31.  
  32.     ~TrieNode() {
  33.       for (int i = 0; i < 26; ++i) delete son[i];
  34.     }
  35.  
  36.     void add(const char *str) {
  37.       if (*str == '\0') num = ++it;
  38.       else if (son[*str - 'a'] == NULL) son[*str - 'a'] = new TrieNode(str + 1);
  39.       else son[*str - 'a']->add(str + 1);
  40.     }
  41.   };
  42.  
  43.   TrieNode root;
  44.   bool fail_ok;
  45.  
  46.   void compute_fail() {
  47.     root.fail = &root;
  48.     deque<TrieNode*> q;
  49.     q.push_back(&root);
  50.     while (!q.empty()) {
  51.       TrieNode *v = q.front();
  52.       q.pop_front();
  53.       for (int i = 0; i < 26; ++i) {
  54.         if (v->son[i] != NULL) {
  55.           q.push_back(v->son[i]);
  56.           TrieNode *tmp = v->fail;
  57.           while (tmp != &root && tmp->son[i] == NULL) tmp = tmp->fail;
  58.           v->son[i]->fail = tmp->son[i] != NULL && tmp->son[i] != v->son[i] ? tmp->son[i] : &root;
  59.         }
  60.       }
  61.     }
  62.   }
  63.  
  64.  public:
  65.   PatternsMatcher() : fail_ok(false) {}
  66.  
  67.   void add_pattern(const char *str) {
  68.     root.add(str);
  69.     fail_ok = false;
  70.   }
  71.  
  72.   void search(const char *str, bool (*callback)(int idx, int pat_idx, void *data), void *data = NULL) {
  73.     if (!fail_ok) compute_fail();
  74.     fail_ok = true;
  75.     TrieNode *v = &root;
  76.     bool stop = false;
  77.     for (int i = 0; *str != '\0' && !stop; ++i, ++str) {
  78.       int j = *str - 'a';
  79.       while (v != &root && v->son[j] == NULL) v = v->fail;
  80.       v = v->son[j] != NULL ? v->son[j] : &root;
  81.       for (TrieNode *u = v; u != &root; u = u->fail) {
  82.         if (u->num > 0 && !callback(i, u->num - 1, data)) {
  83.           stop = true;
  84.           break;
  85.         }
  86.       }
  87.     }
  88.   }
  89.  
  90.   /*
  91.   This function creates an input for Graphviz dot representing a Trie structure.
  92.   Useful while debugging. Maybe it will be useful while hacking the code
  93.   
  94.   void print(FILE *file) {
  95.     deque<deque<TrieNode *> > rank;
  96.     rank.push_back(deque<TrieNode *>());
  97.     rank[0].push_back(&root);
  98.     deque<pair<TrieNode*, unsigned> > q;
  99.     q.push_back(make_pair(&root, 0));
  100.     fprintf(file, "digraph trie {\n");
  101.     while (!q.empty()) {
  102.       pair<TrieNode*, unsigned> p = q.front();
  103.       q.pop_front();
  104.       if (p.first->fail != NULL) {
  105.         fprintf(file, "  \"%p\" -> \"%p\" [style=\"dashed\"];\n", p.first, p.first->fail);
  106.       }
  107.       for (unsigned i = 0; i < 26; ++i) {
  108.         if (p.first->son[i] != NULL) {
  109.           q.push_back(make_pair(p.first->son[i], p.second + 1));
  110.           if (rank.size() == p.second + 1) rank.push_back(deque<TrieNode *>());
  111.           rank.back().push_back(p.first->son[i]);
  112.           fprintf(file, "  \"%p\" -> \"%p\" [label=\" %c\"];\n", p.first, p.first->son[i], i + 'a');
  113.         }
  114.       }
  115.     }
  116.     for (unsigned i = 0; i < rank.size(); ++i) {
  117.       fprintf(file, "  {rank=same; ");
  118.       for (unsigned j = 0; j < rank[i].size(); ++j) {
  119.         fprintf(file, "\"%p\" ", rank[i][j]);
  120.       }
  121.       fprintf(file, "}\n");
  122.     }
  123.     fprintf(file, "}\n");
  124.     fflush(file);
  125.   }*/
  126. };
  127. int PatternsMatcher::TrieNode::it = 0;
  128.  
  129. bool f(int i, int idx, void *data) {
  130.   vector<string> &t = *((vector<string> *) data);
  131.   printf("%s%s\n", string(i - t[idx].size() + 1, ' ').c_str(), t[idx].c_str());
  132.   return true;
  133. }
  134.  
  135. int main() {
  136.   char *str = new char [MAXN];
  137.   int n;
  138.   scanf("%d\n", &n);
  139.   PatternsMatcher x;
  140.   vector<string> t;
  141.   for (int i = 0; i < n; ++i) {
  142.     scanf("%s\n", str);
  143.     x.add_pattern(str);
  144.     t.push_back(str);
  145.   }
  146.   scanf("%s\n", str);
  147.   printf("%s\n", str);
  148.   x.search(str, f, &t);
  149.   delete str;
  150.   return 0;
  151. }
  152.  
Success #stdin #stdout 0.01s 2824KB
comments (?)
stdin
copy 
4
banana
ana
baklazana
anna
bylaannaktorachailabananaorazbaklazanaityle
stdout
copy 
bylaannaktorachailabananaorazbaklazanaityle
    anna
                    ana
                   banana
                      ana
                             baklazana
                                   ana
https://ideone.com/xzYisb
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!