Algorithms : add 04-algorithms_on_strings 02-burrows_wheeler

7 files changed, 41 insertions, 0 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
new file mode 100644
index 0000000..1dbbcc3
--- /dev/null
+++ b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/suffix_array.cpp
@@ -0,0 +1,35 @@
+#include <algorithm>
+#include <iostream>
+#include <string>
+#include <vector>
+#include <utility>
+
+using std::cin;
+using std::cout;
+using std::endl;
+using std::make_pair;
+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;
+}
+
+int main() {
+  string text;
+  cin >> text;
+  vector<int> suffix_array = BuildSuffixArray(text);
+  for (int i = 0; i < suffix_array.size(); ++i) {
+    cout << suffix_array[i] << ' ';
+  }
+  cout << endl;
+  return 0;
+}
diff --git a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample1 b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample1
new file mode 100644
index 0000000..b97cb09
--- /dev/null
+++ b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample1
@@ -0,0 +1 @@
+GAC$
diff --git a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample1.a b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample1.a
new file mode 100644
index 0000000..ee9295b
--- /dev/null
+++ b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample1.a
@@ -0,0 +1 @@
+3 1 2 0 
diff --git a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample2 b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample2
new file mode 100644
index 0000000..37abc16
--- /dev/null
+++ b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample2
@@ -0,0 +1 @@
+GAGAGAGA$
diff --git a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample2.a b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample2.a
new file mode 100644
index 0000000..9e98c55
--- /dev/null
+++ b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample2.a
@@ -0,0 +1 @@
+8 7 5 3 1 6 4 2 0 
diff --git a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample3 b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample3
new file mode 100644
index 0000000..bc4db06
--- /dev/null
+++ b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample3
@@ -0,0 +1 @@
+AACGATAGCGGTAGA$
diff --git a/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample3.a b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample3.a
new file mode 100644
index 0000000..33f85b0
--- /dev/null
+++ b/04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array/tests/sample3.a
@@ -0,0 +1 @@
+15 14 0 1 12 6 4 2 8 13 3 7 9 10 11 5