diff options
Diffstat (limited to '04-algorithms_on_strings/01-suffix_trees/01-trie')
7 files changed, 63 insertions, 0 deletions
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 <string> +#include <iostream> +#include <vector> +#include <map> + +using std::map; +using std::vector; +using std::string; + +typedef map<char, int> edges; +typedef vector<edges> trie; + +trie build_trie(vector<string> & patterns) { + trie t; + // write your code here + return t; +} + +int main() { + size_t n; + std::cin >> n; + vector<string> 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 |