Algorithms : complete 04-algorithms_on_strings 01-suffix_trees

1 files changed, 22 insertions, 2 deletions

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
index 08cfe9b..d5f9483 100644
--- a/04-algorithms_on_strings/01-suffix_trees/01-trie/trie.cpp
+++ b/04-algorithms_on_strings/01-suffix_trees/01-trie/trie.cpp
@@ -12,7 +12,27 @@ typedef vector<edges> trie;
 
 trie build_trie(vector<string> & patterns) {
   trie t;
-  // write your code here
+
+  size_t node;
+  size_t n = 1;
+  t.push_back(edges());
+
+  for (size_t i = 0; i < patterns.size(); i++) {
+      node = 0;
+      const string& pattern = patterns[i];
+      for (size_t j = 0; j < pattern.size(); j++) {
+          char c = pattern[j];
+          int next = t[node][c];
+          if (next != 0) {
+              node = next;
+          } else {
+              t[node][c] = n;
+              node = n;
+              t.push_back(edges());
+              n += 1;
+          }
+      }
+  }
   return t;
 }
 
@@ -34,4 +54,4 @@ int main() {
   }
 
   return 0;
-}
\ No newline at end of file
+}