Algorithms : complete 04-algorithms_on_strings 02-burrows_wheeler

1 files changed, 62 insertions, 4 deletions

diff --git a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/suffix_array.cpp b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/suffix_array.cpp
index 1dbbcc3..2e0ec6d 100644
--- a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/suffix_array.cpp
+++ b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/suffix_array.cpp
@@ -11,16 +11,74 @@ using std::make_pair;
 using std::pair;
 using std::string;
 using std::vector;
+using std::swap;
+
+static void quicksort(const string &s, vector<int> &v, int x, int l, int r)
+{
+    if (l >= r)
+        return;
+
+    int p = l + rand() % (r - l + 1);
+    swap(v[l], v[p]);
+
+    char c = s[v[l] + x];
+    int i = l + 1;
+    int j = r;
+    int k = r;
+    while (i <= j) {
+        int C = s[v[j] + x];
+        if (C < c) {
+            swap(v[i], v[j]);
+            i++;
+        } else if (C > c) {
+            swap(v[j], v[k]);
+            k--;
+            j--;
+        }
+        else
+            j--;
+    }
+
+    quicksort(s, v, x, l, i - 1);
+    quicksort(s, v, x, k + 1, r);
+}
+
+static void sort(const string &s, vector<int> &v, int x, int l, int r)
+{
+    if (l >= r)
+        return;
+
+    quicksort(s, v, x, l, r);
+
+    char c = s[v[l] + x];
+    int ll = l;
+    for (int i = l + 1; i <= r; i++) {
+        char C = s[v[i] + x];
+        if (C != c) {
+            sort(s, v, x + 1, ll, i - 1);
+            ll = i;
+            c = C;
+        }
+    }
+    sort(s, v, x + 1, ll, r);
+}
 
 // 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;
+vector<int> BuildSuffixArray(const string& text)
+{
+    int sz = text.size();
+    vector<int> v;
+    v.reserve(text.size());
+    for (int i = 0; i < sz; i++)
+        v.push_back(i);
+
+    sort(text, v, 0, 0, sz - 1);
+
+    return v;
 }
 
 int main() {