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/01-trie/tests/sample1 | 2 ++ .../01-suffix_trees/01-trie/tests/sample1.a | 3 ++ .../01-suffix_trees/01-trie/tests/sample2 | 4 +++ .../01-suffix_trees/01-trie/tests/sample2.a | 4 +++ .../01-suffix_trees/01-trie/tests/sample3 | 4 +++ .../01-suffix_trees/01-trie/tests/sample3.a | 9 ++++++ .../01-suffix_trees/01-trie/trie.cpp | 37 ++++++++++++++++++++++ 7 files changed, 63 insertions(+) create mode 100644 04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1 create mode 100644 04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1.a create mode 100644 04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2 create mode 100644 04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2.a create mode 100644 04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3 create mode 100644 04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3.a create mode 100644 04-algorithms_on_strings/01-suffix_trees/01-trie/trie.cpp (limited to '04-algorithms_on_strings/01-suffix_trees/01-trie') diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1 b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1 new file mode 100644 index 0000000..15cc060 --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1 @@ -0,0 +1,2 @@ +1 +ATA diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1.a b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1.a new file mode 100644 index 0000000..99ce28c --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample1.a @@ -0,0 +1,3 @@ +0->1:A +1->2:T +2->3:A diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2 b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2 new file mode 100644 index 0000000..509298a --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2 @@ -0,0 +1,4 @@ +3 +AT +AG +AC diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2.a b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2.a new file mode 100644 index 0000000..e9b94b5 --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample2.a @@ -0,0 +1,4 @@ +0->1:A +1->4:C +1->3:G +1->2:T diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3 b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3 new file mode 100644 index 0000000..b454c19 --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3 @@ -0,0 +1,4 @@ +3 +ATAGA +ATC +GAT diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3.a b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3.a new file mode 100644 index 0000000..b789e0f --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/tests/sample3.a @@ -0,0 +1,9 @@ +0->1:A +0->7:G +1->2:T +2->3:A +2->6:C +3->4:G +4->5:A +7->8:A +8->9:T diff --git a/04-algorithms_on_strings/01-suffix_trees/01-trie/trie.cpp b/04-algorithms_on_strings/01-suffix_trees/01-trie/trie.cpp new file mode 100644 index 0000000..08cfe9b --- /dev/null +++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/trie.cpp @@ -0,0 +1,37 @@ +#include +#include +#include +#include + +using std::map; +using std::vector; +using std::string; + +typedef map edges; +typedef vector trie; + +trie build_trie(vector & patterns) { + trie t; + // write your code here + return t; +} + +int main() { + size_t n; + std::cin >> n; + vector patterns; + for (size_t i = 0; i < n; i++) { + string s; + std::cin >> s; + patterns.push_back(s); + } + + trie t = build_trie(patterns); + for (size_t i = 0; i < t.size(); ++i) { + for (const auto & j : t[i]) { + std::cout << i << "->" << j.second << ":" << j.first << "\n"; + } + } + + return 0; +} \ No newline at end of file -- cgit v1.2.3