- 【模板】字典树 1
求助 trie!
- 2021-9-25 14:00:09 @
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
bool end=0;
int next[30];
};
vector<node>trie;
node emp;
bool find(string str){
int nd=1;
bool found=1;
for(int i=0;i<str.size();i++){
if(trie[nd].next[str[i]-'a']==-1){
found=0;
trie.push_back(emp);
trie[nd].next[str[i]-'a']=trie.size()-1;
}
nd=trie[nd].next[str[i]-'a'];
}
if(!trie[nd].end) found=0,trie[nd].end=1;
return found;
}
signed main(){
emp.end=0;
for(int i=0;i<30;i++) emp.next[i]=-1;
trie.push_back(emp);
trie.push_back(emp);
int cnt=0;
int n;
cin>>n;
for(int i=1;i<=n;i++){
string k;
cin>>k;
if(!find(k)) cnt++;
}
cout<<cnt;
return 0;
}
4 条评论
-
xyf LV 5 @ 2021-10-1 7:19:38
ok,谢谢大佬!
-
2021-9-25 17:10:27@
vector 的 push_back 常数过大,预先 resize 就可以了吧。
-
2021-9-25 17:10:02@
提问的时候麻烦说清楚,看了眼提交记录才发现你是 TLE。😑
-
2021-9-25 14:26:33@
find
函数的倒数第二行trie[nd].end=false
的时候应该让found=1
吧。
- 1
信息
- ID
- 180
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 2655
- 已通过
- 355
- 上传者