diff options
Diffstat (limited to '04-algorithms_on_strings/02-burrows_wheeler/04-suffix_array')
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 |