From 2cb378d70cd847491680e7768798169ce3f93f00 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Wed, 5 Oct 2016 22:23:54 +0200 Subject: Improve trie code. --- string/trie.cpp | 21 +++++++++------------ 1 file changed, 9 insertions(+), 12 deletions(-) (limited to 'string/trie.cpp') diff --git a/string/trie.cpp b/string/trie.cpp index 24a21b2..5ee7a87 100644 --- a/string/trie.cpp +++ b/string/trie.cpp @@ -5,21 +5,18 @@ struct node { node() { for(int i = 0; i < 26; i++) e[i] = NULL; } }; -void insert(node *root, string *txt, int s) { - if(s == txt->length()) root->c++; +void insert(node *root, string &txt, int s) { // Laufzeit: O(|txt|) + if(s == (int)txt.size()) root->c++; else { - int idx = (int)(*txt[s] - 'a'); - if(root->e[idx] == NULL) { - root->e[idx] = new node(); - } + int idx = (int)(txt[s] - 'a'); + if(root->e[idx] == NULL) root->e[idx] = new node(); insert(root->e[idx], txt, s+1); } } -int contains(node *root, string *txt, int s) { - if(s == txt->length()) return root->c; - int idx = (int)(*txt[s] - 'a'); - if(root->e[idx] != NULL) { - return contains(root->e[idx], txt, s+1); - } else return 0; +int contains(node *root, string &txt, int s) { // Laufzeit: O(|txt|) + if(s == txt.size()) return root->c; + int idx = (int)(txt[s] - 'a'); + if(root->e[idx] != NULL) return contains(root->e[idx], txt, s + 1); + else return 0; } -- cgit v1.2.3