add suffix tree and some geo3d

zimpha · zimpha · commit e8fa2852c987 · 2016-08-12T00:36:27.000+08:00
diff --git a/README.md b/README.md
@@ -13,7 +13,7 @@ Collections of some commonly used algorithms.
   + [x] SA-IS
   + [ ] DC3
   + [ ] GSACA
-+ [ ] 后缀树
++ [x] 后缀树
 + [x] 后缀自动机
 + [ ] 子序列自动机
 + [ ] AC自动机
diff --git a/computational-geometry/geo3d.cc b/computational-geometry/geo3d.cc
@@ -0,0 +1,63 @@
+#include <cmath>
+#include <cstdio>
+
+typedef double flt;
+
+const flt eps = 1e-8;
+int sgn(flt x) {return x < -eps ? -1 : x > eps;}
+
+struct Point {
+  flt x, y, z;
+  Point() {}
+  Point(flt x, flt y, flt z): x(x), y(y), z(z) {}
+  bool operator < (const Point &rhs) const {
+    return x < rhs.x || (x == rhs.x && y < rhs.y) || (x == rhs.x && y == rhs.y && z < rhs.z);
+  }
+  Point operator + (const Point &rhs) const {
+    return Point(x + rhs.x, y + rhs.y, z + rhs.z);
+  }
+  Point operator - (const Point &rhs) const {
+    return Point(x - rhs.x, y - rhs.y, z - rhs.z);
+  }
+  Point operator * (const flt k) const {
+    return Point(x * k, y * k, z * k);
+  }
+  Point operator / (const flt k) const {
+    return Point(x / k, y / k, z / k);
+  }
+  flt dot(const Point &rhs) const {
+    return x * rhs.x + y * rhs.y + z * rhs.z;
+  }
+  Point det(const Point &rhs) const {
+    return Point(y * rhs.z - z * rhs.y, z * rhs.x - x * rhs.z, x * rhs.y - y * rhs.x);
+  }
+  flt sqrlen() const {
+    return x * x + y * y + z * z;
+  }
+  flt len() const {
+    return sqrt(sqrlen());
+  }
+  void read() {
+    scanf("%lf%lf%lf", &x, &y, &z);
+  }
+  void print() {
+    printf("%.10f %.10f %.10f\n", x, y, z);
+  }
+} A, B, C, D;
+
+// 判断点C是否在直线AB上
+bool dotsInline(const Point &A, const Point &B, const Point &C) {
+  return sgn((B - A).det(C - A).len()) == 0;
+}
+
+// 判断直线AB和CD是否平行
+bool is_parallel(const Point &A, const Point &B, const Point &C, const Point &D) {
+  return sgn((B - A).det(D - C).len()) == 0;
+}
+
+// 判断直线AB和CD的交点, 如果直线异面, 返回的是两直线的垂线在AB上的垂足
+// 需要保证AB和CD不平行.
+Point intersect(const Point &A, const Point &B, const Point &C, const Point &D) {
+  Point p0 = (C - A).det(D - C), p1 = (B - A).det(D - C);
+  return A + (B - A) * (p0.dot(p1) / p1.sqrlen());
+}
diff --git a/string-utility/suffix-tree.cc b/string-utility/suffix-tree.cc
@@ -21,8 +21,8 @@ namespace SuffixTree {
     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;}
+    void go(int o) {u = u->go[o]; pos -= u->len;}
+    bool can(int o) {return u->go[o] && pos > u->go[o]->len;}
   } last;
   int s[SIZE], n;
   node *new_node(int st, int len) {
@@ -63,4 +63,12 @@ namespace SuffixTree {
       else last.u = last.u->link ? last.u->link : rt;
     }
   }
+  // count the number of distinct substrings
+  int count() {
+    int ret = 0;
+    for (int i = 1; i < sz - pool; ++i) {
+      ret += std::min(n - pool[i].st, pool[i].len);
+    }
+    return ret;
+  }
 }
