Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.8 kB
5
Indexable
Never
#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;
}
Leave a Comment