Algorithms : complete 04-algorithms_on_strings 02-burrows_wheeler

1 files changed, 138 insertions, 8 deletions

diff --git a/04-algorithms_on_strings/02-burrows_wheeler/02-bwtinverse/bwtinverse.cpp b/04-algorithms_on_strings/02-burrows_wheeler/02-bwtinverse/bwtinverse.cpp
index 3ec7c54..7c6ec56 100644
--- a/04-algorithms_on_strings/02-burrows_wheeler/02-bwtinverse/bwtinverse.cpp
+++ b/04-algorithms_on_strings/02-burrows_wheeler/02-bwtinverse/bwtinverse.cpp
@@ -8,18 +8,148 @@ using std::cout;
 using std::endl;
 using std::string;
 using std::vector;
+using std::swap;
 
-string InverseBWT(const string& bwt) {
-  string text = "";
+static bool debug = false;
 
-  // write your code here
+class InverseBwt
+{
+private:
+    vector<int> indexes;
+    const string &s;
+    int sz;
+    int starts[4] = {0, 0, 0, 0};
 
-  return text;
-}
+public:
+
+    InverseBwt(const string& text) : s(text), sz(text.size()) {
+        string ss = s;
+        quicksort(ss, 0, sz - 1);
+
+        indexes.reserve(sz);
+        int count[] = {0, 0, 0, 0};
+
+        for (int i = 0; i < sz; i++) {
+            int c = 0;
+            switch(s[i]) {
+                case 'A':
+                    c = count[0];
+                    count[0] += 1;
+                    break;
+                case 'C':
+                    c = count[1];
+                    count[1] += 1;
+                    break;
+                case 'G':
+                    c = count[2];
+                    count[2] += 1;
+                    break;
+                case 'T':
+                    c = count[3];
+                    count[3] += 1;
+                    break;
+                default:
+                    break;
+            }
+            indexes.push_back(c);
+
+            switch(ss[i]) {
+                case 'A':
+                    if (starts[0] == 0 )
+                        starts[0] = i;
+                    break;
+                case 'C':
+                    if (starts[1] == 0 )
+                        starts[1] = i;
+                    break;
+                case 'G':
+                    if (starts[2] == 0 )
+                        starts[2] = i;
+                    break;
+                case 'T':
+                    if (starts[3] == 0 )
+                        starts[3] = i;
+                    break;
+                default:
+                    break;
+            }
+        }
+
+        if (debug) {
+            for (int i = 0; i < sz; i++) {
+                cout << ss[i] << ";" << s[i] << ";" << indexes[i] << endl;
+            }
+            cout << starts[0] << endl;
+            cout << starts[1] << endl;
+            cout << starts[2] << endl;
+            cout << starts[3] << endl;
+        }
+    }
+
+    string solve() {
+        string ret = s;
+
+        ret[sz - 1] = '$';
+        for (int i = 0,  j = sz - 2; j >= 0; j--) {
+            ret[j] = s[i];
+            char ch = s[i];
+            i = indexes[i];
+            switch(ch) {
+                case 'A':
+                    i += starts[0];
+                    break;
+                case 'C':
+                    i += starts[1];
+                    break;
+                case 'G':
+                    i += starts[2];
+                    break;
+                case 'T':
+                    i += starts[3];
+                    break;
+                default:
+                    break;
+            }
+        }
+
+        return ret;
+    }
+
+private:
+
+    void quicksort(string &s, int l, int r) {
+        if (l >= r)
+            return;
+
+        int p = l + rand() % (r - l + 1);
+        swap(s[l], s[p]);
+
+        char c = s[l];
+        int i = l + 1;
+        int j = r;
+        int k = r;
+        while (i <= j) {
+            int C = s[j];
+            if (C < c) {
+                swap(s[i], s[j]);
+                i++;
+            } else if (C > c) {
+                swap(s[j], s[k]);
+                k--;
+                j--;
+            }
+            else
+                j--;
+        }
+
+        quicksort(s, l, i - 1);
+        quicksort(s, k + 1, r);
+    }
+};
 
 int main() {
-  string bwt;
-  cin >> bwt;
-  cout << InverseBWT(bwt) << endl;
+  string text;
+  cin >> text;
+  cout << InverseBwt(text).solve() << endl;
   return 0;
 }