Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<unordered_map>
- using namespace std;
- class Node
- {
- public:
- char data;
- unordered_map<char, Node*> children;
- bool terminal;
- //constructor
- Node(char c)
- {
- data=c;
- terminal=false;
- }
- };
- class Trie
- {
- Node *root;
- public:
- Trie()
- {
- root=new Node('\0');
- }
- void insert(char *w)
- {
- Node *temp=root;
- for(int i=0; w[i]!='\0'; i++)
- {
- char ch=w[i];
- if(temp->children.count(ch))
- temp=temp->children[ch];
- else
- {
- Node *n=new Node(ch);
- temp->children[ch]=n;
- temp=n;
- }
- }
- temp->terminal=true;
- }
- bool search(char *w)
- {
- Node *temp=root;
- for(int i=0; w[i]!='\0'; i++)
- {
- char ch=w[i];
- if(temp->children.count(ch)==0)
- return false;
- else temp=temp->children[ch];
- }
- return temp->terminal;
- }
- };
- int main()
- {
- char words[][20]={"I", "am", "Iron", "Man", "&", "myself", "GROOT!!"};
- Trie t;
- for(int i=0; i<7; i++)
- t.insert(words[i]);
- char w[10];
- cin>>w;
- if(t.search(w))
- cout<<"PRESENT in the Trie Data Structure";
- else cout<<"ABSENT in the Trie Data Structure";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement