fork(1) download
copy 
  1. #include <string>
  2. #include <vector>
  3. #include <memory>
  4. #include <cstring>
  5. #include <iostream>
  6.  
  7. template<size_t K>
  8. struct vertex
  9. {
  10.         int next[K];    // index to the next vertex by char
  11.         bool leaf;      // is terminal
  12.         int p;          // parent vertex
  13.         char pch;       // parent char which leads to this vertex
  14.         int link;       // suffix link
  15.         int go[K];      // automaton goto function
  16.         int out;        // suffix link to leaf
  17.         int key_idx;    // index of key
  18. };
  19.  
  20.  
  21. template<size_t K = 26, size_t NMAX = 500>
  22. class automaton
  23. {
  24. public:
  25.         automaton()
  26.         {
  27.                 t[0].p = t[0].link = -1;
  28.                 memset(t[0].next, 255, sizeof t[0].next);
  29.                 memset(t[0].go, 255, sizeof t[0].go);
  30.                 sz = 1;
  31.         }
  32.  
  33.         void add_string (const std::string& s) {
  34.                 int v = 0;
  35.                 for (size_t i = 0; i < s.length(); ++i)
  36.                 {
  37.                         char c = s[i]-'a';
  38.                         if (t[v].next[c] == -1) {
  39.                                 memset (t[sz].next, 255, sizeof t[sz].next);
  40.                                 memset (t[sz].go, 255, sizeof t[sz].go);
  41.                                 t[sz].link = -1;
  42.                                 t[sz].p = v;
  43.                                 t[sz].pch = c;
  44.                                 t[sz].leaf = false;
  45.                                 t[sz].out = -1;
  46.                                 t[v].next[c] = sz++;
  47.                         }
  48.                         v = t[v].next[c];
  49.                 }
  50.                 t[v].leaf = true;
  51.  
  52.                 keys.push_back(s);
  53.                 t[v].key_idx = keys.size() - 1;
  54.         }
  55.  
  56.         int get_link(int v) {
  57.                 if (t[v].link == -1)
  58.                         if (v == 0 || t[v].p == 0)
  59.                                 t[v].link = 0;
  60.                         else
  61.                                 t[v].link = go(get_link(t[v].p), t[v].pch);
  62.                 return t[v].link;
  63.         }
  64.  
  65.         int go(int v, char c) {
  66.                 if(t[v].go[c] == -1)
  67.                         if(t[v].next[c] != -1)
  68.                                 t[v].go[c] = t[v].next[c];
  69.                         else
  70.                                 t[v].go[c] = v==0 ? 0 : go(get_link(v), c);
  71.                 return t[v].go[c];
  72.         }
  73.  
  74.         int out(int v)
  75.         {
  76.                 if(t[v].out == -1)
  77.                 {
  78.                         int u = get_link(v);
  79.                         if(t[u].leaf)
  80.                                 t[v].out = u;
  81.                         else if(u == 0)
  82.                                 t[v].out = 0;
  83.                         else
  84.                                 t[v].out = out(u);
  85.                 }
  86.  
  87.                 return t[v].out;
  88.         }
  89.  
  90.         void check(int v, int i)
  91.         {
  92.                 for(int u = v; v != 0; v = out(v))
  93.                 {
  94.                         if(t[u].leaf)
  95.                         {
  96.                                 int k = t[u].key_idx;
  97.                                 std::cout << (i - keys[k].length() + 1)
  98.                                           << " "
  99.                                           << keys[k]
  100.                                           << std::endl;
  101.                         }
  102.                 }
  103.         }
  104.  
  105.         void check2(int v, int i)
  106.         {
  107.                 {
  108.                         if(t[v].leaf)
  109.                         {
  110.                                 int k = t[v].key_idx;
  111.                                 std::cout << (i - keys[k].length() + 1)
  112.                                           << " "
  113.                                           << keys[k]
  114.                                           << std::endl;
  115.                         }
  116.                 }
  117.         }
  118.  
  119.         void find_all_occurrences(const std::string& text)
  120.         {
  121.                 int v = 0;
  122.                 for(int i = 0; i < text.length(); ++i)
  123.                 {
  124.                         v = go(v, text[i] - 'a');
  125.                         check(v, i + 1);
  126.                 }
  127.         }
  128.  
  129.  
  130. private:
  131.         vertex<K> t[NMAX+1];
  132.         int sz;
  133.         std::vector<std::string> keys;
  134. };
  135.  
  136. //
  137. //class Solution {
  138. //public:
  139. //        std::vector<std::string> wordBreak(std::string s,
  140. //                                           std::vector<std::string>& wordDict) {
  141. //
  142. //
  143. //        }
  144. //};
  145.  
  146. void _test_1()
  147. {
  148.         std::vector<std::string> dict = {"apple", "pen", "applepen",
  149.                                          "pine", "pineapple"};
  150.  
  151.         std::string s = "pineapplepenapple";
  152.  
  153.  
  154.         automaton<> m;
  155.  
  156.         for(const auto& k : dict)
  157.                 m.add_string(k);
  158.  
  159.         m.find_all_occurrences(s);
  160. }
  161.  
  162. void _test_2()
  163. {
  164.         std::vector<std::string> dict = {"abc", "bcdc", "cccb",
  165.                                          "bcdd", "bbbc"};
  166.  
  167.         std::string s = "abcdcbcddbbbcccbbbcccbb";
  168.  
  169.  
  170.         automaton<> m;
  171.  
  172.         for(const auto& k : dict)
  173.                 m.add_string(k);
  174.  
  175.         m.find_all_occurrences(s);
  176. }
  177.  
  178. int main()
  179. {
  180. 	std::cout<<"Test 1:"<<std::endl;
  181. 	_test_1();
  182. 	std::cout<<"Test 2:"<<std::endl;
  183. 	_test_2();
  184.  
  185. 	return 0;
  186. }
Success #stdin #stdout 0s 4580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test 1:
1 pine
1 pineapple
1 pineapple
5 applepen
5 applepen
13 apple
Test 2:
1 abc
2 bcdc
6 bcdd
10 bbbc
13 cccb
16 bbbc
19 cccb
https://ideone.com/t0ynyV
language:
C++ (gcc 8.3)
created:
5 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!