Allenlzcoder
diff --git a/‎README.md
Lines changed: 2 additions & 1 deletion b/‎README.md
Lines changed: 2 additions & 1 deletion
diff --git a/‎others/mod_int.cc renamed to ‎others/ModInt.cc b/‎others/mod_int.cc renamed to ‎others/ModInt.cc
diff --git a/‎string-utility/ext_kmp.cc renamed to ‎string-utility/ext-kmp.cc b/‎string-utility/ext_kmp.cc renamed to ‎string-utility/ext-kmp.cc
diff --git a/‎string-utility/lyndon-word-factorization.cc
Lines changed: 50 additions & 0 deletions b/‎string-utility/lyndon-word-factorization.cc
Lines changed: 50 additions & 0 deletions
diff --git a/‎string-utility/suffix-tree.cc
Lines changed: 66 additions & 0 deletions b/‎string-utility/suffix-tree.cc
Lines changed: 66 additions & 0 deletions
@@ -17,7 +17,8 @@ Collections of some commonly used algorithms.
 + [x] 后缀自动机
 + [ ] 子序列自动机
 + [ ] AC自动机
-+ [x] Minimum Palindromic Factorization
++ [x] Palindromic Factorization
++ [x] Lyndon Word Factorization
 + [ ] Square Factorization
 + [ ] Repetitions
 
 
@@ -0,0 +1,50 @@
+#include <vector>
+#include <string>
+#include <cstring>
+
+/**
+ * Duval's Lyndon Factorization Algorithm.
+ *
+ * the input string s should end with a zero symbol
+ * return a list of begins of prime strings
+ **/
+std::vector<int> duval(char s[]){
+  std::vector<int> ret;
+  int n = strlen(s) + 1; // zero used here
+  int start = 0, mid = 1, cur = 0;
+  ret.push_back(0);
+  for (int i = 0; i < n; ++i){
+    if (s[i] == s[cur]){
+      if (++cur == mid) cur = start;
+    } else if (s[i] > s[cur]){
+      mid = i + 1;
+      cur = start;
+    } else if (s[i] < s[cur]){
+      int temp = mid - start;
+      while (start + temp <= i){
+        start += temp;
+        ret.push_back(start);
+      }
+      i = cur = start;
+      mid = start + 1;
+    }
+  }
+  return ret;
+}
+
+/**
+ * Duval's Algorithm for Generating Lyndon Words
+ *
+ * generate the Lyndon words of length at most n with a given alphabet size m
+ * in lexicographic order.
+ **/
+void lyndon_generate(int n, int m) {
+  char z = 'a' + m - 1, s[1000];
+  s[0] = 'a' - 1;
+  for (int i = 1, x = 1; ; ++i) {
+    s[x - 1]++; s[x] = 0;
+    puts(s);
+    for (int j = x; j < n; ++j) s[j] = s[j - x];
+    for (x = n; s[x - 1] == z; --x);
+  }
+}
@@ -0,0 +1,66 @@
+#include <cstring>
+
+/**
+ * Ukkonen's Online Construction of Suffix Tree
+ **/
+namespace SuffixTree {
+  static const int SIZE = 100000 + 10, SIGMA = 26, inf = 1e9;
+  struct node {
+    node *go[26], *link, *fa;
+    int st, len;
+    node() {}
+    void clr() {
+      st = 0, len = inf;
+      link = fa = NULL;
+      memset(go, 0, sizeof(go));
+    }
+  } pool[SIZE], *rt, *sz;
+
+  struct position {
+    node *u;
+    int pos;
+    position() {}
+    position(node* u, int pos): u(u), pos(pos) {}
+    void go(int o) {u = u->go[o], pos -= u->len;}
+    bool can(int o) {return pos > u->go[o]->len;}
+  } last;
+  int s[SIZE], n;
+  node *new_node(int st, int len) {
+    sz->clr();
+    sz->st = st, sz->len = len;
+    return sz++;
+  }
+  void init() {
+    n = 0, sz = pool;
+    rt = new_node(0, inf);
+    last = position(rt, 0);
+  }
+  void add(int c) {
+    s[n++] = c;
+    last.pos++;
+    for (node* p = rt; last.pos; ) {
+      while (last.can(s[n - last.pos])) last.go(s[n - last.pos]);
+      int o = s[n - last.pos];
+      node* &v = last.u->go[o];
+      int t = s[v == NULL ? 0 : v->st + last.pos - 1];
+      if (v == NULL) {
+        v = new_node(n - last.pos, inf);
+        p->link = last.u;
+        p = rt;
+      } else if (t == c) {
+        p->link = last.u;
+        return;
+      } else {// split edge
+        node *u = new_node(v->st, last.pos - 1);
+        u->go[c] = new_node(n - 1, inf);
+        u->go[t] = v;
+        v->st += last.pos - 1;
+        v->len -= last.pos - 1;
+        p->link = v = u;
+        p = u;
+      }
+      if (last.u == rt) --last.pos;
+      else last.u = last.u->link ? last.u->link : rt;
+    }
+  }
+}