add Lempel-Ziv Factorization and subsequence automaton

zimpha · zimpha · commit 0bef8b3c061f · 2016-08-12T18:56:12.000+08:00
diff --git a/README.md b/README.md
@@ -8,18 +8,17 @@ Collections of some commonly used algorithms.
 + [x] manacher
 + [x] 字符串hash
 + [x] EERTREE
-+ [ ] 后缀数组
-  + [x] 倍增
++ [x] 后缀数组
+  + [x] Prefix Doubling
   + [x] SA-IS
-  + [ ] DC3
-  + [ ] GSACA
 + [x] 后缀树
 + [x] 后缀自动机
-+ [ ] 子序列自动机
++ [x] 子序列自动机
 + [ ] AC自动机
 + [x] Palindromic Factorization
 + [x] Lyndon Word Factorization
 + [ ] Square Factorization
++ [x] Lempel-Ziv Factorization
 + [ ] Repetitions
 
 ## Graph Algorithms
diff --git a/string-utility/SequenceAutomaton.cc b/string-utility/SequenceAutomaton.cc
diff --git a/string-utility/lempel-ziv-factorization.cc b/string-utility/lempel-ziv-factorization.cc
@@ -0,0 +1,48 @@
+#include <cstring>
+#include <vector>
+#include <utility>
+
+using PII = std::pair<int, int>;
+
+/**
+ * Implement this paper:
+ *   Simpler and Faster Lempel Ziv Factorization
+ *
+ * s: input string
+ * sa: suffix array of s
+ * rk: inverse suffix array
+ * return a list of (len, prevOcc)
+ **/
+std::vector<PII> LempelZiv(char s[], int sa[], int rk[]) {
+  int n = strlen(s);
+  std::vector<int> psv(n + 1), nsv(n + 1), stack;
+  // computer psv and nsv from suffix array
+  for (int i = 0; i < n; ++i) {
+    int x = sa[i];
+    while (!stack.empty() && sa[stack.back()] > x) {
+      nsv[stack.back()] = x;
+      stack.pop_back();
+    }
+    psv[i] = stack.empty() ? -1 : sa[stack.back()];
+    stack.push_back(i);
+  }
+  while (!stack.empty()) {
+    nsv[stack.back()] = -1;
+    stack.pop_back();
+  }
+  // computer Lempel-Ziv Factorization
+  std::vector<PII> lz;
+  lz.push_back(PII(0, s[0]));
+  for (int p = 1; p < n; ) {
+    int lpf = 0, prev = psv[p];
+    for (auto &j: {psv[p], nsv[p]}) if (~j) {
+      int l = 0;
+      while (p + l < n && s[j + l] == s[p + l]) ++l;
+      if (l > lpf) lpf = l, prev = j;
+    }
+    if (lpf) lz.push_back(PII(lpf, prev));
+    else lz.push_back(PII(1, s[p]));
+    p += std::max(1, lpf);
+  }
+  return lz;
+}
diff --git a/string-utility/sa-is.cc b/string-utility/sa-is.cc
@@ -7,11 +7,14 @@
  *
  * time complexity: O(n)
  */
+#include <algorithm>
+
 namespace SA {
+const static int N = 100000 + 10;
 int sa[N], rk[N], ht[N], s[N<<1], t[N<<1], p[N], cnt[N], cur[N];
 #define pushS(x) sa[cur[s[x]]--] = x
 #define pushL(x) sa[cur[s[x]]++] = x
-#define inducedSort(v) fill_n(sa, n, -1); fill_n(cnt, m, 0);                \
+#define inducedSort(v) std::fill_n(sa, n, -1); std::fill_n(cnt, m, 0);      \
   for (int i = 0; i < n; i++) cnt[s[i]]++;                                  \
   for (int i = 1; i < m; i++) cnt[i] += cnt[i-1];                           \
   for (int i = 0; i < m; i++) cur[i] = cnt[i]-1;                            \
@@ -39,7 +42,7 @@ void sais(int n, int m, int *s, int *t, int *p) {
 template<typename T>
 int mapCharToInt(int n, const T *str) {
   int m = *max_element(str, str+n);
-  fill_n(rk, m+1, 0);
+  std::fill_n(rk, m+1, 0);
   for (int i = 0; i < n; i++) rk[str[i]] = 1;
   for (int i = 0; i < m; i++) rk[i+1] += rk[i];
   for (int i = 0; i < n; i++) s[i] = rk[str[i]] - 1;
diff --git a/string-utility/subsequence-automaton.cc b/string-utility/subsequence-automaton.cc
@@ -0,0 +1,27 @@
+/**
+ * Directed acyclic subsequence graph 
+ *   - recognize all the subsequences of a string.
+ *
+ * time complexity: O(n * \sigma)
+ **/
+#include <cstring>
+#include <algorithm>
+
+struct DASG {
+  static const int SIZE = 100000 + 10, SIGMA = 26;
+  struct Node{
+    Node *ch[SIGMA];
+    Node() {memset(ch, 0, sizeof(ch));}
+  } pool[SIZE], *sz, *rt, *last[SIGMA];
+  void init() {
+    sz = pool; rt = sz++;
+    std::fill(last, last + SIGMA, rt);
+  } 
+  void add(int x) {
+    Node *np = sz++;
+    for (Node *p = last[x]; p < np; ++p) {
+      if (!p->ch[x]) p->ch[x] = np;
+    }
+    last[x] = np;
+  }
+};
diff --git a/string-utility/suffix-automaton.cc b/string-utility/suffix-automaton.cc
