Written by Anonymous
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dbl;
#define fr(x,a,b) for(ll x=a;x<b;x++)
#define PB push_back
#define MP make_pair
#define mod 1000000007
#define gmax LLONG_MAX
#define gmin LLONG_MIN
#define INF 2e9
#define N 26
#define MAX(a,b,c) max(max(a,b),c)
#define MIN(a,b,c) min(min(a,b),c)
#define SZ(x) x.size()
struct Trie{
struct Trie *child[N]; // reference to a to z alphabets(N=26)
bool is_EOW; // flag for indicating end of word or not
~Trie(){
cout<<"\nMemory Freed!\n";
}
};
struct Trie *get_node(){
struct Trie *ptr = new Trie;
ptr->is_EOW=false;
fr(i,0,N) ptr->child[i]=NULL;
return ptr;
}
// inserts a word in the trie data structure
void insert(struct Trie *root,string word){
struct Trie *ptr=root;
ll pos;
fr(i,0,word.size()){
pos=word[i]-'a';
if(ptr->child[pos]==NULL) ptr->child[pos]=get_node();
ptr=ptr->child[pos];
}
ptr->is_EOW=true;
}
// checks if the word is present as complete word
bool complete_search(struct Trie *root,string word){
struct Trie *ptr=root;
ll pos;
fr(i,0,word.size()){
pos=word[i]-'a';
if(ptr->child[pos]==NULL) return false;
ptr=ptr->child[pos];
}
return (ptr!=NULL && ptr->is_EOW==true);
}
// checks if the word is present as complete word or prefix of some other word
bool prefix_search(struct Trie *root,string word){
struct Trie *ptr=root;
ll pos;
fr(i,0,word.size()){
pos=word[i]-'a';
if(ptr->child[pos]==NULL) return false;
ptr=ptr->child[pos];
}
return (ptr!=NULL);
}
bool is_leaf(struct Trie *node){
return (node->is_EOW);
}
bool is_free(struct Trie *node){
fr(i,0,26) if(node->child[i]!=NULL) return false;
return true;
}
// delets a word from the true data structure
bool delete_word(struct Trie *root,string word,ll ind){
if(root==NULL) return false;
if(ind==SZ(word)){
if(root->is_EOW){
root->is_EOW=false;
if(is_free(root)) return true;
return false;
}
}
else{
ll pos=word[ind]-'a';
if(root->child[pos]==NULL) return false;
if(delete_word(root->child[pos],word,ind+1)){
delete root->child[pos];
//root->child[pos]=NULL;
return (!is_leaf(root) && is_free(root));
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string list[5]={"a","abc","abccd","egh","eghik"};
struct Trie *root=get_node();
fr(i,0,5) insert(root,list[i]);
fr(i,0,5){
if(complete_search(root,list[i])){
cout<<list[i]<<" is found as complete word\n";
}
}
cout<<"\n";
string new_words[3]={"ab","eghi","a"};
fr(i,0,3){
if(complete_search(root,new_words[i])){
cout<<new_words[i]<<" is found as complete word\n";
}
}
cout<<"\n";
fr(i,0,3){
if(prefix_search(root,new_words[i])){
cout<<new_words[i]<<" is found as prefix\n";
}
}
cout<<"\n";
cout<<delete_word(root,"abccd",0)<<"\n";
cout<<complete_search(root,"abccd");
return 0;
}