Algorithms : complete 04-algorithms_on_strings 04-suffix_array

4 files changed, 455 insertions, 36 deletions

diff --git a/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp b/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp
index 13121ae..4ac7afd 100644
--- a/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp
+++ b/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp
@@ -7,13 +7,23 @@ using std::cin;
 using std::string;
 using std::vector;
 
-// Find all occurrences of the pattern in the text and return a
-// vector with all positions in the text (starting from 0) where 
-// the pattern starts in the text.
-vector<int> find_pattern(const string& pattern, const string& text) {
-  vector<int> result;
-  // Implement this function yourself
-  return result;
+vector<int> find_pattern(const string& pattern, const string& text)
+{
+    vector<int> result;
+    string s = pattern + "$" + text;
+    vector<int> prefixes(s.size());
+    int border = 0;
+    int ps = pattern.size();
+
+    for (int i = 1; i < s.size(); i++) {
+        while ((border > 0) && (s[i] != s[border]))
+            border = prefixes[border - 1];
+        prefixes[i] = border = ((s[i] == s[border]) ? (border + 1) : 0);
+        if (border == ps)
+            result.push_back(i - 2 * ps);
+    }
+
+    return result;
 }
 
 int main() {
diff --git a/04-algorithms_on_strings/04-suffix_array/02-suffix_array_long/suffix_array_long.cpp b/04-algorithms_on_strings/04-suffix_array/02-suffix_array_long/suffix_array_long.cpp
index 1dbbcc3..7235bbe 100644
--- a/04-algorithms_on_strings/04-suffix_array/02-suffix_array_long/suffix_array_long.cpp
+++ b/04-algorithms_on_strings/04-suffix_array/02-suffix_array_long/suffix_array_long.cpp
@@ -12,15 +12,121 @@ using std::pair;
 using std::string;
 using std::vector;
 
-// Build suffix array of the string text and
-// return a vector result of the same length as the text
-// such that the value result[i] is the index (0-based)
-// in text where the i-th lexicographically smallest
-// suffix of text starts.
-vector<int> BuildSuffixArray(const string& text) {
-  vector<int> result;
-  // Implement this function yourself
-  return result;
+static int $ = 0;
+static int A = 1;
+static int C = 2;
+static int G = 3;
+static int T = 4;
+
+static inline int toInt(char c)
+{
+    int ret = 0;
+    switch(c) {
+        case 'A': ret = A; break;
+        case 'C': ret = C; break;
+        case 'G': ret = G; break;
+        case 'T': ret = T; break;
+    }
+    return ret;
+}
+
+vector<int> BuildSuffixArray(const string& text)
+{
+    int sz = text.size();
+    vector<int> v0(sz);
+    vector<int> v1(sz);
+    vector<int> v2(sz);
+    vector<int> v3(sz);
+    vector<int> v4(sz);
+
+    // count sort text[i]
+    vector<int> &count = v0;
+    for (int i = 0; i < sz; i++)
+        count[toInt(text[i])] += 1;
+    for(int i = 1; i < 5; i++)
+        count[i] += count[i - 1];
+
+    vector<int> &order = v1;
+    for (int i = sz - 1; i >= 0; i--) {
+        int x = toInt(text[i]);
+        count[x] -= 1;
+        order[count[x]] = i;
+    }
+
+    // compute classes
+    int cl = 0;
+    vector<int> &classes = v2;
+    classes[order[0]] = cl;
+    for (int i = 1; i < sz; i++) {
+        if (text[order[i]] != text[order[i - 1]])
+            cl += 1;
+        classes[order[i]] = cl;
+    }
+
+    /* cout << text << endl; */
+    /* cout << "$ : " << count[$] << endl; */
+    /* cout << "A : " << count[A] << endl; */
+    /* cout << "C : " << count[C] << endl; */
+    /* cout << "G : " << count[G] << endl; */
+    /* cout << "T : " << count[T] << endl; */
+    /* cout << "order" << endl; */
+    /* for (int i = 0; i < sz; i++) */
+    /*     cout << order[i] << " "; */
+    /* cout << endl; */
+    /* cout << "classes" << endl; */
+    /* for (int i = 0; i < sz; i++) */
+    /*     cout << classes[i] << " "; */
+    /* cout << endl; */
+
+    int l = 1;
+    vector<int> &nOrder = v3;
+    vector<int> &nClasses = v4;
+    while (l < sz) {
+        // count sort classes
+        for (int i = 0; i < sz; i++)
+            count[i] = 0;
+        for (int i = 0; i < sz; i++)
+            count[classes[i]] += 1;
+        for(int i = 1; i < sz; i++)
+            count[i] += count[i - 1];
+        for (int i = sz - 1; i >= 0; i--) {
+            int x = (order[i] - l + sz) % sz;
+            int cl = classes[x];
+            count[cl] -= 1;
+            nOrder[count[cl]] = x;
+        }
+        if(order == v1) {
+            order = v3;
+            nOrder = v1;
+        } else {
+            order = v1;
+            nOrder = v3;
+        }
+
+        // update classes
+        nClasses[order[0]] = 0;
+        for (int i = 1; i < sz; i++) {
+            int cur = order[i];
+            int prev = order[i - 1];
+            int mid = (cur + l) % sz;
+            int midPrev = (prev + l) % sz;
+            if (classes[cur] != classes[prev] || classes[mid] != classes[midPrev])
+                nClasses[cur] = nClasses[prev] + 1;
+            else
+                nClasses[cur] = nClasses[prev];
+        }
+        if(classes == v2) {
+            classes = v4;
+            nClasses = v2;
+        } else {
+            classes = v2;
+            nOrder = v4;
+        }
+
+        l *= 2;
+    }
+
+    return order;
 }
 
 int main() {
diff --git a/04-algorithms_on_strings/04-suffix_array/03-suffix_array_matching/suffix_array_matching.cpp b/04-algorithms_on_strings/04-suffix_array/03-suffix_array_matching/suffix_array_matching.cpp
index 204218c..74fa0ee 100644
--- a/04-algorithms_on_strings/04-suffix_array/03-suffix_array_matching/suffix_array_matching.cpp
+++ b/04-algorithms_on_strings/04-suffix_array/03-suffix_array_matching/suffix_array_matching.cpp
@@ -7,21 +7,187 @@ using std::cin;
 using std::string;
 using std::vector;
 
-vector<int> BuildSuffixArray(const string& text) {
-  vector<int> order;
+static int $ = 0;
+static int A = 1;
+static int C = 2;
+static int G = 3;
+static int T = 4;
 
-  // write your code here
+static inline int toInt(char c)
+{
+    int ret = 0;
+    switch(c) {
+        case 'A': ret = A; break;
+        case 'C': ret = C; break;
+        case 'G': ret = G; break;
+        case 'T': ret = T; break;
+    }
+    return ret;
+}
+
+vector<int> BuildSuffixArray(const string& text)
+{
+    int sz = text.size();
+    vector<int> v0(sz);
+    vector<int> v1(sz);
+    vector<int> v2(sz);
+    vector<int> v3(sz);
+    vector<int> v4(sz);
+
+    // count sort text[i]
+    vector<int> &count = v0;
+    for (int i = 0; i < sz; i++)
+        count[toInt(text[i])] += 1;
+    for(int i = 1; i < 5; i++)
+        count[i] += count[i - 1];
+
+    vector<int> &order = v1;
+    for (int i = sz - 1; i >= 0; i--) {
+        int x = toInt(text[i]);
+        count[x] -= 1;
+        order[count[x]] = i;
+    }
+
+    // compute classes
+    int cl = 0;
+    vector<int> &classes = v2;
+    classes[order[0]] = cl;
+    for (int i = 1; i < sz; i++) {
+        if (text[order[i]] != text[order[i - 1]])
+            cl += 1;
+        classes[order[i]] = cl;
+    }
+
+    int l = 1;
+    vector<int> &nOrder = v3;
+    vector<int> &nClasses = v4;
+    while (l < sz) {
+        // count sort classes
+        for (int i = 0; i < sz; i++)
+            count[i] = 0;
+        for (int i = 0; i < sz; i++)
+            count[classes[i]] += 1;
+        for(int i = 1; i < sz; i++)
+            count[i] += count[i - 1];
+        for (int i = sz - 1; i >= 0; i--) {
+            int x = (order[i] - l + sz) % sz;
+            int cl = classes[x];
+            count[cl] -= 1;
+            nOrder[count[cl]] = x;
+        }
+        if(order == v1) {
+            order = v3;
+            nOrder = v1;
+        } else {
+            order = v1;
+            nOrder = v3;
+        }
+
+        // update classes
+        nClasses[order[0]] = 0;
+        for (int i = 1; i < sz; i++) {
+            int cur = order[i];
+            int prev = order[i - 1];
+            int mid = (cur + l) % sz;
+            int midPrev = (prev + l) % sz;
+            if (classes[cur] != classes[prev] || classes[mid] != classes[midPrev])
+                nClasses[cur] = nClasses[prev] + 1;
+            else
+                nClasses[cur] = nClasses[prev];
+        }
+        if(classes == v2) {
+            classes = v4;
+            nClasses = v2;
+        } else {
+            classes = v2;
+            nOrder = v4;
+        }
 
-  return order;
+        l *= 2;
+    }
+
+    return order;
+}
+
+vector<int> _lcp(const string& s, const vector<int>& order)
+{
+    int sz = order.size();
+    vector<int> v(sz - 1);
+    vector<int> r(sz); // order from i
+    for (int i = 0; i < sz; i++)
+        r[order[i]] = i;
+
+    int lcp = 0;
+    int suffix = order[0];
+    for (int i = 0; i < sz; i++) {
+        int x = r[suffix];
+        if (x == sz - 1) {
+            lcp = 0;
+        } else {
+            int nextSuffix = order[x + 1];
+            if (lcp > 0) lcp -= 1;
+            while ((suffix + lcp < sz) && (nextSuffix + lcp < sz)) {
+                if (s[suffix + lcp] == s[nextSuffix+ lcp])
+                    lcp += 1;
+                else
+                    break;
+            }
+            v[x] = lcp;
+        }
+        suffix = (suffix + 1) % sz;
+    }
+
+    return v;
 }
 
+vector<int> FindOccurrences(const string& pattern, const string& text, const vector<int>& suffix_array)
+{
+    vector<int> result;
 
-vector<int> FindOccurrences(const string& pattern, const string& text, const vector<int>& suffix_array) {
-  vector<int> result;
+    int sz = text.size();
+    int pz = pattern.size();
+    int l = 0;
+    int r = sz;
+    while (l < r) {
+        int mid = (l + r) / 2;
+        int k = suffix_array[mid];
+        bool lower = false;
+        for (int j = 0; j < pz; j++) {
+            if (pattern[j] == text[k + j])
+                continue;
+            if (pattern[j] > text[k + j])
+                lower = true;
+            break;
+        }
+        if (lower)
+            l = mid + 1;
+        else
+            r = mid;
+    }
+
+    int s = l;
+    r = sz;
+    while (l < r) {
+        int mid = (l + r) / 2;
+        int k = suffix_array[mid];
+        bool lower = false;
+        for (int j = 0; j < pz; j++) {
+            if (pattern[j] == text[k + j])
+                continue;
+            if (pattern[j] < text[k + j])
+                lower = true;
+            break;
+        }
+        if (lower)
+            r = mid;
+        else
+            l = mid + 1;
+    }
 
-  // write your code here
+    for (int i = s; i < r; i++)
+        result.push_back(suffix_array[i]);
 
-  return result;
+    return result;
 }
 
 int main() {
diff --git a/04-algorithms_on_strings/04-suffix_array/04-suffix_tree_from_array/suffix_tree_from_array.cpp b/04-algorithms_on_strings/04-suffix_array/04-suffix_tree_from_array/suffix_tree_from_array.cpp
index ca9fdb5..4ac4658 100644
--- a/04-algorithms_on_strings/04-suffix_array/04-suffix_tree_from_array/suffix_tree_from_array.cpp
+++ b/04-algorithms_on_strings/04-suffix_array/04-suffix_tree_from_array/suffix_tree_from_array.cpp
@@ -22,8 +22,9 @@ struct Edge {
   // corresponding to the label of this edge.
   int end;
 
-  Edge(int node_, int start_, int end_) : node(node_), start(start_), end(end_) {}
-  Edge(const Edge& e) : node(e.node), start(e.start), end(e.end) {}
+  Edge(int node_, int start_, int end_) :
+      node(node_), start(start_), end(end_) {}
+  /* Edge(const Edge& e) : node(e.node), start(e.start), end(e.end) {} */
 };
 
 // Build suffix tree of the string text given its suffix array suffix_array
@@ -37,15 +38,112 @@ struct Edge {
 // must be represented by Edge(1, 6, 7). This edge must be present in the vector tree[0]
 // (corresponding to the root node), and it should be the first edge in the vector 
 // (because it has the smallest first character of all edges outgoing from the root).
-map<int, vector<Edge> > SuffixTreeFromSuffixArray(
-    const vector<int>& suffix_array,
-    const vector<int>& lcp_array,
-    const string& text) {
-  map<int, vector<Edge> > tree;
-  // Implement this function yourself
-  return tree;
-}
+map<int, vector<Edge>> SuffixTreeFromSuffixArray(
+        const vector<int>& suffix_array,
+        const vector<int>& lcp_array,
+        const string& text)
+{
+    map<int, vector<Edge>> tree;
+    vector<int> hierarchy;
+    int sz = suffix_array.size();
+    int n = 0;
+    int parent = 0;
+    int idx = 0;
+    int prevLcp = 0;
+    hierarchy.push_back(0);
+
+    // add '$'
+    tree[parent].push_back(Edge(++n, suffix_array[0], sz));
 
+    // add following suffixes
+    /* for (int i = 1; i < 6; i++) { */
+    for (int i = 1; i < suffix_array.size(); i++) {
+        int start = suffix_array[i];
+        int lcp = lcp_array[i - 1];
+
+        if (lcp == 0) {
+            // add to root
+            parent = 0;
+            vector<Edge>& v = tree[parent];
+            idx = v.size();
+            v.push_back(Edge(++n, start, sz));
+            hierarchy.resize(1);
+        } else if (lcp == prevLcp) {
+            // add to parent
+            tree[parent].push_back(Edge(++n, start + lcp, sz));
+            idx++;
+        } else {
+            int s;
+            int l = (lcp - prevLcp);
+            bool push = true;
+            Edge& last = tree[parent][idx];
+            if (l > 0) {
+                s = start + lcp;
+                // push 2 new edges under last
+                parent = last.node;
+                vector<Edge>& v = tree[parent];
+                v.push_back(Edge(++n, last.start + l, sz));
+                v.push_back(Edge(++n, s, sz));
+                idx = 1;
+                // update split edge
+                last.end = s;
+                last.start = s - l;
+                // set branch update values
+                /* l = prevLcp; */
+                /* s = last.start; */
+            } else {
+                // find good parent
+                while (l < 0) {
+                    hierarchy.resize(hierarchy.size() - 1);
+                    Edge& e = tree[hierarchy.back()].back();
+                    l += (e.end - e.start);
+                }
+                parent = hierarchy.back();
+                idx = tree[parent].size() - 1;
+                prevLcp = (lcp - l);
+                if (l == 0) {
+                    // add to parent
+                    tree[parent].push_back(Edge(++n, start + lcp, sz));
+                    idx++;
+                    // set branch update values
+                    /* l = lcp; */
+                    /* s = start + lcp; */
+                    push = false;
+                } else {
+                    // set new split edge
+                    vector<Edge>& v = tree[parent];
+                    Edge old = v.back();
+                    v.pop_back();
+                    v.push_back(Edge(++n, start + prevLcp, start + lcp));
+                    // feed new split edge
+                    parent = n;
+                    vector<Edge>& w = tree[parent];
+                    old.start += l;
+                    w.push_back(old);
+                    w.push_back(Edge(++n, start + lcp, sz));
+                    idx = 1;
+                    // set branch update values
+                    /* l = prevLcp; */
+                    /* s = start + prevLcp; */
+                }
+            }
+            // update branch
+            /* for (int i = hierarchy.size() - 2; (l > 0 && i >= 0); i--) { */
+            /*     Edge& e = tree[hierarchy[i]].back(); */
+            /*     int d = e.end - e.start; */
+            /*     e.end = s; */
+            /*     s -= d; */
+            /*     e.start = s; */
+            /*     l -= d; */
+            /* } */
+            if (push)
+                hierarchy.push_back(parent);
+        }
+        prevLcp = lcp;
+    }
+
+    return tree;
+}
 
 int main() {
   char buffer[200001];
@@ -62,7 +160,6 @@ int main() {
   // Build the suffix tree and get a mapping from 
   // suffix tree node ID to the list of outgoing Edges.
   map<int, vector<Edge> > tree = SuffixTreeFromSuffixArray(suffix_array, lcp_array, text);
-  printf("%s\n", buffer);
   // Output the edges of the suffix tree in the required order.
   // Note that we use here the contract that the root of the tree
   // will have node ID = 0 and that each vector of outgoing edges
@@ -85,6 +182,27 @@ int main() {
   //   }
   // }
   //
+/* #define GRAPH */
+#ifdef GRAPH
+  fprintf(stderr, "suffixes :\n");
+  for (int i = 0; i < suffix_array.size(); i++) {
+      if (i == 0) {
+          fprintf(stderr, "%2d      : ", suffix_array[i]);
+      } else {
+          fprintf(stderr, "%2d (%2d) : ", suffix_array[i], lcp_array[i - 1]);
+      }
+      for (int j = suffix_array[i]; j < text.size(); j++)
+          fprintf(stderr, "%c", text[j]);
+      fprintf(stderr, "\n");
+  }
+  printf("digraph G {\nlabel=\"%s\n", text.c_str());
+  for (int i = 0; i < text.size(); i++)
+      printf("%d ", i);
+  printf("\"\n");
+#else
+  printf("%s\n", buffer);
+#endif
+
   vector<pair<int, int> > stack(1, make_pair(0, 0));    
   while (!stack.empty()) {
     pair<int, int> p = stack.back();
@@ -98,8 +216,27 @@ int main() {
     if (edge_index + 1 < edges.size()) {
       stack.push_back(make_pair(node, edge_index + 1));
     }
-    printf("%d %d\n", edges[edge_index].start, edges[edge_index].end);
     stack.push_back(make_pair(edges[edge_index].node, 0));
+#ifdef GRAPH
+    if (edge_index == 0) {
+        for (int i = 0; i < edges.size(); i++) {
+            const Edge& e = edges[i];
+            printf(" %d [ label=\"%d : %d,%d\n", e.node, e.node, e.start, e.end);
+            if (e.start >= 0) {
+                for (int j = e.start; j < e.end; j++)
+                    printf("%c", text[j]);
+            }
+            printf("\" ]\n");
+            printf("%d -> %d\n", node, e.node);
+        }
+    }
+#else
+    printf("%d %d\n", edges[edge_index].start, edges[edge_index].end);
+#endif
   }
+#ifdef GRAPH
+  printf("}\n");
+#endif
+
   return 0;
 }