用map构造字典树并用c++代码表示出来
时间: 2023-07-27 14:33:14 浏览: 42
好的,下面是用C++代码实现的字典树:
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int cnt = 0;
int trie[maxn][26];
bool is_end[maxn];
void insert(string s) {
int p = 0;
for(int i = 0; i < s.size(); i++) {
int u = s[i] - 'a';
if(!trie[p][u]) trie[p][u] = ++cnt;
p = trie[p][u];
}
is_end[p] = true;
}
bool search(string s) {
int p = 0;
for(int i = 0; i < s.size(); i++) {
int u = s[i] - 'a';
if(!trie[p][u]) return false;
p = trie[p][u];
}
return is_end[p];
}
int main() {
int n;
cin >> n;
while(n--) {
string s;
cin >> s;
insert(s);
}
string t;
cin >> t;
if(search(t)) cout << "YES\n";
else cout << "NO\n";
return 0;
}
```
上述代码中,`trie` 数组存储了字典树的每个节点,`is_end` 数组标记了每个节点是否为单词结尾。`insert` 函数用于将一个单词插入字典树中,`search` 函数用于查找一个单词是否在字典树中出现过。