Algorithms : add 04-algorithms_on_strings 01-suffix_trees

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