Untitled
unknown
plain_text
a year ago
1.8 kB
7
Indexable
#include<iostream> #include<string> using namespace std; struct Node{ Node *child[26]; int count; //count number of prefix word bool endWord; string s; Node(){ for(int i = 0; i < 26; i++){ child[i] = nullptr; } count = 0; endWord = false; s = ""; } }; struct Trie{ Node *root; Trie(){ root = new Node(); } void insert(string inp){ int index; Node *current = root; for(char c : inp){ index = c - 'a'; if(current->child[index] == nullptr) current->child[index] = new Node(); current = current->child[index]; current->count++; } current->endWord = true; current->s = inp; } bool search(string inp){ int index; Node *current = root; for(char c : inp){ index = c - 'a'; if(current->child[index] == nullptr) return false; current = current->child[index]; } return current->endWord == true; } int countPrefix(string inp){ int index; Node *current = root; for(char c : inp){ index = c - 'a'; if(current->child[index] == nullptr) return 0; current = current->child[index]; } return current->count; } void printNode(Node *current){ //print string current and all child of node if(current == nullptr) return; if(current->endWord) cout << current->s << endl; for(int i = 0; i < 26; i++){ printNode(current->child[i]); } } void printAll(){ printNode(root); } }; int main(){ Trie t; t.insert("abc"); t.insert("bcd"); t.insert("abcd"); t.insert("acd"); bool x1 = t.search("acd"); bool x2 = t.search("acc"); int x3 = t.countPrefix("ab"); int x4 = t.countPrefix("a"); int x5 = t.countPrefix("c"); cout << x1 << " " << x2 << " " << x3 << " " << x4 << " " << x5 << endl; t.printAll(); return 0; }
Editor is loading...
Leave a Comment