Algorithms : complete 04-algorithms_on_strings 02-burrows_wheeler

1 files changed, 98 insertions, 7 deletions

diff --git a/04-algorithms_on_strings/02-burrows_wheeler/01-bwt/bwt.cpp b/04-algorithms_on_strings/02-burrows_wheeler/01-bwt/bwt.cpp
index f3b0497..6b1c94b 100644
--- a/04-algorithms_on_strings/02-burrows_wheeler/01-bwt/bwt.cpp
+++ b/04-algorithms_on_strings/02-burrows_wheeler/01-bwt/bwt.cpp
@@ -8,18 +8,109 @@ using std::cout;
 using std::endl;
 using std::string;
 using std::vector;
+using std::swap;
 
-string BWT(const string& text) {
-  string result = "";
+static bool debug = false;
 
-  // write your code here
+class Bwt
+{
+private:
+    vector<int> v;
+    const string &s;
+    int sz;
 
-  return result;
-}
+    void print(int n)
+    {
+        cout << "print : " << n << endl;
+        for (int i = 0; i < v.size(); i++)
+            cout << v[i] << ";" << s[(v[i] + n) % sz] << endl;
+    }
+
+    void print()
+    {
+        cout << "print : " << endl;
+        for (int i = 0; i < v.size(); i++) {
+            for (int j = 0; j < sz; j++)
+                cout << s[(v[i] + j) % sz];
+            cout << endl;
+        }
+    }
+
+public:
+
+    Bwt(const string& text) : s(text), sz(text.size()) {
+        v.reserve(s.size());
+        for (int i = 0; i < s.size(); i++)
+            v.push_back(i);
+        if (debug) print();
+    }
+
+    string solve() {
+        sort(0, 0, v.size() - 1);
+        if (debug) print();
+
+        string ret = "";
+        for (int i = 0; i < v.size(); i++)
+            ret += s[(v[i] + sz - 1) % sz];
+        return ret;
+    }
+
+private:
+    void sort(int x, int l, int r)
+    {
+        if (debug) cout << " sort: " << x  << ";" << l << ";" << r << endl;
+        if (l >= r)
+            return;
+
+        quicksort(x, l, r);
+        if (debug) print();
+
+        char c = s[(v[l] + x) % sz];
+        int ll = l;
+        for (int i = l + 1; i <= r; i++) {
+            char C = s[(v[i] + x) % sz];
+            if (C != c) {
+                sort(x + 1, ll, i - 1);
+                ll = i;
+                c = C;
+            }
+        }
+        sort(x + 1, ll, r);
+    }
+
+    void quicksort(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) % sz];
+        int i = l + 1;
+        int j = r;
+        int k = r;
+        while (i <= j) {
+            int C = s[(v[j] + x ) % sz];
+            if (C < c) {
+                swap(v[i], v[j]);
+                i++;
+            } else if (C > c) {
+                swap(v[j], v[k]);
+                k--;
+                j--;
+            }
+            else
+                j--;
+        }
+
+        quicksort(x, l, i - 1);
+        quicksort(x, k + 1, r);
+    }
+};
 
 int main() {
   string text;
   cin >> text;
-  cout << BWT(text) << endl;
+  cout << Bwt(text).solve() << endl;
   return 0;
-}
\ No newline at end of file
+}