add bit-lcs and clcs

zimpha · zimpha · commit 024dc465b799 · 2016-08-14T00:05:47.000+08:00
diff --git a/README.md b/README.md
@@ -20,6 +20,8 @@ Collections of some commonly used algorithms.
 + [ ] Square Factorization
 + [x] Lempel-Ziv Factorization
 + [ ] Repetitions
++ [x] CLCS
++ [x] bit-LCS
 
 ## Graph Algorithms
 
@@ -140,3 +142,4 @@ Collections of some commonly used algorithms.
 + [x] Frobenius Equations
 + [x] 最长上升子序列
 + [ ] Stern–Brocot tree
++ [ ] 直线下格点
diff --git a/string-utility/bit-lcs.cc b/string-utility/bit-lcs.cc
@@ -0,0 +1,77 @@
+/**
+ * Bit-String Longest Common Subsequence LCS Algorithm
+ *
+ * http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/86.IPL.html
+ *
+ * time complexity: O(nm/w)
+ **/
+#include <bits/stdc++.h>
+typedef long long LL;
+
+const int MAXN = 2000 + 10, SIGMA = 26;
+const int W = 62;
+int M = 33;
+struct Bitset {
+  LL u[34];
+  void clr() {
+    memset(u, 0, sizeof(u));
+  }
+  void set(int x) {
+    u[x / W] |= 1ll << (x % W);
+  }
+  Bitset operator |(const Bitset &r) const {
+    Bitset s;
+    for (int i = 0; i < M; ++ i) {
+      s.u[i] = u[i] | r.u[i];
+    }
+    return s;
+  }
+  void gao(const Bitset &r) {
+    for (int i = 0; i < M; ++ i) {
+      u[i] = (u[i] ^ r.u[i]) & r.u[i];
+    }
+  }
+  void sub(const Bitset &r) {
+    for (int i = 0; i < M; ++ i) u[i] = r.u[i] - u[i];
+    for (int i = 0; i < M; ++ i) if (u[i] < 0) {
+      u[i] += 1ll << W; u[i + 1] --;
+    }
+  }
+  void shl() {
+    for (LL i = 0, c(1); i < M; ++ i) {
+      u[i] <<= 1; u[i] |= c;
+      c = u[i] >> W & 1;
+      u[i] ^= c << W;
+    }
+  }
+  int cnt() const {
+    int c(0);
+    for (int i = 0; i < M; ++ i) {
+      c += __builtin_popcountll(u[i]);
+    }
+    return c;
+  }
+} row, as[SIGMA], x;
+
+
+int main() {
+  char S[MAXN], T[MAXN];
+  for (int i = 0; i < SIGMA; ++i) as[i].clr();
+  scanf("%s%s", S, T);
+  int n = strlen(S), m = strlen(T);
+  for (int i = 0; i < n; ++ i) {
+    as[S[i] - 'a'].set(i);
+  }
+  M = n / W + (n % W != 0);
+  row.clr();
+  for (int i = 0; i < m; ++i) {
+    for (int j = 0; j < M; ++j) {
+      x.u[j] = row.u[j] | as[T[i] - 'a'].u[j];
+    }
+    row.shl();
+    row.sub(x);
+    row.gao(x);
+    printf("%d\n", row.cnt());
+  }
+  return 0;
+}
diff --git a/string-utility/cyclic-longest-common-string.cc b/string-utility/cyclic-longest-common-string.cc
@@ -0,0 +1,54 @@
+/**
+ * Solving Cyclic Longest Common Subsequence in Quadratic Time
+ * https://arxiv.org/pdf/1208.0396v3.pdf
+ *
+ * time complexity: O(nm)
+ **/
+#include <cstring>
+#include <algorithm>
+
+const int N = 4000 + 10;
+int dp[N][N], from[N][N];
+
+int clcs(char s[], char t[]) {
+  int n = strlen(s), m = strlen(t);
+  auto eq = [&](int a, int b) {
+    return s[(a - 1) % n] == t[(b - 1) % m];
+  };
+  dp[0][0] = from[0][0] = 0;
+  for (int i = 0; i <= n * 2; ++i) {
+    for (int j = 0; j <= m; ++j) {
+      dp[i][j] = 0;
+      if (j && dp[i][j - 1] > dp[i][j]) {
+        dp[i][j] = dp[i][j - 1];
+        from[i][j] = 0;
+      }
+      if (i && j && eq(i, j) && dp[i - 1][j - 1] + 1 > dp[i][j]) {
+        dp[i][j] = dp[i - 1][j - 1] + 1;
+        from[i][j] = 1;
+      }
+      if (i && dp[i - 1][j] > dp[i][j]) {
+        dp[i][j] = dp[i - 1][j];
+        from[i][j] = 2;
+      }
+    }
+  }
+  int ret = 0;
+  for (int i = 0; i < n; ++i) {
+    ret = std::max(ret, dp[i + n][m]);
+    // re-root
+    int x = i + 1, y = 0;
+    while (y <= m && from[x][y] == 0) ++y;
+    for (; y <= m && x <= n * 2; ++x) {
+      from[x][y] = 0, --dp[x][m];
+      if (x == n * 2) break;
+      for (; y <= m; ++y) {
+        if (from[x + 1][y] == 2) break;
+        if (y + 1 <= m && from[x + 1][y + 1] == 1) {
+          ++y; break;
+        }
+      }
+    }
+  }
+  return ret;
+}
