Workspace/trie.cpp at master · gods-mack/Workspace · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78


#include<bits/stdc++.h>
using namespace std;

struct node {
	char data;
	node *children[26];
	int wc;

};

struct node *getNode() {
		node *n = new node;
		n->wc = 0;
		for(int i=0; i<26; i++) {
			n->children[i] = NULL;
		}
		return n;

}


void insert(node *root, string s) {


	node *tmp  = root;


	for(int i = 0; i < (int)s.length(); i++) {
		int ind = s[i] - 'a';
		if(!tmp->children[ind]){
			tmp->children[ind] = getNode();
			tmp->children[ind]->data = s[i];
		}
		tmp = tmp->children[ind];
	}
	tmp->wc = 1;


}

bool search(node *root, string s) {

	node *tmp = root;
	for(int i=0; i<(int)s.length(); i++) {

		int ind = s[i] - 'a';
		tmp = tmp->children[ind];
		if(tmp->data != s[i]) {
			return false;
		}

	}
	return (tmp!=NULL && tmp->wc == 1);
}

int main() {

	node *root = nullptr;
	root = getNode();

	int n; cin>>n;
	for(int i =0; i < n; i++) {
		string s;
		cin>>s;

		insert(root,s);
	}

	if(search(root,"manish")){
		cout<<"found..";
	}
	else{
		cout<<"no found..";
	}

}