From 26e4da9f87a7330d96bbeea0d47d875d3a96b1f8 Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Mon, 14 Nov 2016 06:35:14 +0100 Subject: Algorithms : complete 04-algorithms_on_strings 01-suffix_trees --- .../01-suffix_trees/01-trie/trie.cpp | 24 ++++++++++++++++++++-- 1 file changed, 22 insertions(+), 2 deletions(-) (limited to '04-algorithms_on_strings/01-suffix_trees/01-trie') 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 trie; trie build_trie(vector & 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 +} -- cgit v1.2.3