Data-structure---Tree/Trie.cpp at main · regismeyssonnier/Data-structure---Tree · 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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// Trie.cpp : Ce fichier contient la fonction 'main'. L'exécution du programme commence et se termine à cet endroit.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Node {

	Node *son[256];
	bool end_mark = false;

	Node() {
		for (int i = 0; i < 256; i++) {
			son[i] = NULL;
		}
		end_mark = false;
	}

};

struct trie {
	Node* root;

	trie(){
		root = new Node();
	}


	void Add(string s) {

		Node* curr = root;

		for (int i = 0; i < s.length(); i++) {
			if (curr->son[(int)s[i]] == NULL) {
				curr->son[(int)s[i]] = new Node();

			}

			curr = curr->son[(int)s[i]];

		}

		curr->end_mark = true;

	}

	bool Search(string s) {
		Node* curr = root;
		if (s.length() == 0)return false;

		for (int i = 0; i < s.length(); i++) {

			if (curr->end_mark && i < s.length() -1) {
				return true;
			}
			curr = curr->son[(int)s[i]];
			if (curr == NULL) {
				return false;
			}

		}

		return false;

	}

	bool Exist(string s) {

		Node* curr = root;
		if (s.length() == 0)return false;

		for (int i = 0; i < s.length(); i++) {

			curr = curr->son[(int)s[i]];
			if (curr == NULL ) {

				return false;
			}

		}

		if (curr != NULL && curr->end_mark)
			return true;
		else return false;


	}


};


int main()
{
	trie t;

	t.Add("aadfabbb");
	t.Add("aaab");
	t.Add("bbbc");
	t.Add("bcbcggfg");

	if (t.Search("bbbcfgegr")) {
		cout << "have prefix " << endl;
	}
	else {
		cout << "have not a prefix " << endl;
	}

	if (t.Exist("bcbcggfg")) {
		cout << "exists " << endl;
	}
	else {
		cout << "doesnt exist " << endl;
	}


}

// Exécuter le programme : Ctrl+F5 ou menu Déboguer > Exécuter sans débogage