Playground
#include <iostream> #include <string> using namespace std; struct TrieNode { int prefixes; //broj na prefiksi koi pominuvaat niz ovoj element int words; //broj na zborovi koi zavrshuvaat kaj ovoj element struct TrieNode *child[26]; }; //funkcija koja sozdava "TrieNode" i gi inicijalizira vrednostite struct TrieNode *createNode() { struct TrieNode *node = new TrieNode(); node->prefixes = 0; node->words = 0; for (int i=0; i < 26; i++) { node->child[i] = NULL; } return node; } //funkcija za dodavanje na nov zbor void insertWord(TrieNode *root, string word) { struct TrieNode *current = root; for (int i=0; i < word.size(); i++) { int index = word[i] - 'a'; if (!current->child[index]) { //nema vrska do slednoto nivo current->child[index] = createNode(); } //odi do sledniot znak, vo slednoto nivo //(shto ili vekje postoi, ili go sozdavame so prethodniot chekor) current->prefixes++; current = current->child[index]; } //imame dodadeno sve so prethodniot for ciklus //i (current) pokazuva onamu kade shto zavrshuva zborot, //pa samo treba da go zgolemime soodvetniot brojac (kolku //pati e dodaden tochno ovoj zbor vo drvoto) current->words++; } //funkcija koja broi kolku pati zborot "word" e dodaden vo drvoto int countWords(TrieNode *root, string word) { struct TrieNode *current = root; for (int i=0; i < word.size(); i++) { int index = word[i] - 'a'; if (!current->child[index]) { //nema vrska, pa brojot e 0 (nema pat vo drvoto) return 0; } //inaku, odi do slednoto nivo current = current->child[index]; } //dojdovme do krajot, pa samo treba da go vratime brojot na zborovi return current->words; } //funkcija koja broi kolku zborovi vo drvoto go imaat soodvetniot "prefix" int countPrefixes(TrieNode *root, string prefix) { struct TrieNode *current = root; for (int i=0; i < prefix.size(); i++) { int index = prefix[i] - 'a'; if (!current->child[index]) { //nema vrska, pa brojot na prefiksi e 0 return 0; } //inaku, odi do slednoto nivo current = current->child[index]; } //dojdovme do krajot, pa samo treba da go vratime brojot na prefiksi return current->prefixes; } int main() { struct TrieNode *root = createNode(); insertWord(root, string("daca")); insertWord(root, string("doo")); insertWord(root, string("www")); insertWord(root, string("zzz")); insertWord(root, string("zzz")); cout << countPrefixes(root, string("xyz")) << endl; //pechati 0 cout << countPrefixes(root, string("w")) << endl; //pechati 1 ("www") cout << countPrefixes(root, string("ww")) << endl; //pechati 1 ("www") cout << countPrefixes(root, string("d")) << endl; //pechati 2 ("daca", "doo") cout << countWords(root, string("hello")) << endl; //pechati 0 cout << countWords(root, string("daca")) << endl; //pechati 1 ("daca") cout << countWords(root, string("www")) << endl; //pechati 1 ("www") cout << countWords(root, string("zzz")) << endl; //pechati 2 ("zzz", "zzz") cout << countWords(root, string("z")) << endl; //pechati 0 return 0; }
Input data
Program output
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!