From 45188449a04a1455ade01caf470e43a926d752aa Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Mon, 14 Nov 2016 06:35:05 +0100 Subject: Algorithms : add 04-algorithms_on_strings 01-suffix_trees --- .../01-suffix_trees/04-suffix_tree/suffix_tree.cpp | 30 ++++++++++++++++++++++ .../01-suffix_trees/04-suffix_tree/tests/sample1 | 1 + .../01-suffix_trees/04-suffix_tree/tests/sample1.a | 2 ++ .../01-suffix_trees/04-suffix_tree/tests/sample2 | 1 + .../01-suffix_trees/04-suffix_tree/tests/sample2.a | 5 ++++ .../01-suffix_trees/04-suffix_tree/tests/sample3 | 1 + .../01-suffix_trees/04-suffix_tree/tests/sample3.a | 12 +++++++++ 7 files changed, 52 insertions(+) create mode 100644 04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/suffix_tree.cpp create mode 100644 04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1 create mode 100644 04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1.a create mode 100644 04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2 create mode 100644 04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2.a create mode 100644 04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3 create mode 100644 04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3.a (limited to '04-algorithms_on_strings/01-suffix_trees/04-suffix_tree') diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/suffix_tree.cpp b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/suffix_tree.cpp new file mode 100644 index 0000000..5d9e2f1 --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/suffix_tree.cpp @@ -0,0 +1,30 @@ +#include +#include +#include +#include + +using std::cin; +using std::cout; +using std::endl; +using std::map; +using std::string; +using std::vector; + +// Build a suffix tree of the string text and return a vector +// with all of the labels of its edges (the corresponding +// substrings of the text) in any order. +vector ComputeSuffixTreeEdges(const string& text) { + vector result; + // Implement this function yourself + return result; +} + +int main() { + string text; + cin >> text; + vector edges = ComputeSuffixTreeEdges(text); + for (int i = 0; i < edges.size(); ++i) { + cout << edges[i] << endl; + } + return 0; +} diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1 b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1 new file mode 100644 index 0000000..09574e8 --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1 @@ -0,0 +1 @@ +A$ diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1.a b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1.a new file mode 100644 index 0000000..29f8526 --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample1.a @@ -0,0 +1,2 @@ +$ +A$ diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2 b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2 new file mode 100644 index 0000000..e73cda6 --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2 @@ -0,0 +1 @@ +ACA$ diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2.a b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2.a new file mode 100644 index 0000000..e374793 --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample2.a @@ -0,0 +1,5 @@ +$ +CA$ +A +$ +CA$ diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3 b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3 new file mode 100644 index 0000000..cd7fdc4 --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3 @@ -0,0 +1 @@ +ATAAATG$ diff --git a/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3.a b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3.a new file mode 100644 index 0000000..2a60baa --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/04-suffix_tree/tests/sample3.a @@ -0,0 +1,12 @@ +$ +T +G$ +AAATG$ +G$ +A +T +G$ +AAATG$ +A +TG$ +ATG$ -- cgit v1.2.3