<>trie树(用法和总结)

- 南昌理工集训队

*
啥是trie树(找张图)

- 这是trie树的存储基本原理。

就是用树状形式储存每一个字符,并保存节点,来进行的查找。
这样的做法是很高效的(可以看出,因为字符的重复利用率很高)

- trie树的作用

1 储存字符和查找字符(很高效,最基本的用法)
2 求两字符前后缀是否满足字串(很重要,也是核心的用法)
3 求前后缀有几个相同的前缀或后缀
4 异或对(难,我还没学会,别问,问就是智商太低(;′⌒`) )
qwq 肯定很疑惑为什么不用KMP大法。(0.0)
(当然也可以用KMP,但当数量很多很慢啊,要一个一个枚举,难过)

- 模板提供

重要环节到了 ,怎么用代码实现?

*
第一个是储存(插入trie树)
void insert(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u =
str[i] - 'a'; if (!son[p][u]) son[p][u] = ++ idx; p = son[p][u]; } cnt[p] ++ ; }
* 第二个 查找字符 // 查询字符串 bool query(char *str) { int p = 0; for (int i = 0; str[i];
i++ ) { int u = str[i] - 'a'; if (!son[p][u]) return false; p = son[p][u]; }
return cut[p]; }
这是主要的两个打法,其余的都是自己去维护trie树。

* 来一道模版题

#include<iostream> using namespace std; const int N=1e6+10; int son[N][26],cut[
N],idx; string op,str; void insert(string str){ int p=0; for(int i=0;i<str.size(
);i++){ int u=str[i]-'a'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; } cut[p]
++; } int query(string str){ int p=0; for(int i=0;i<str.size();i++){ int u=str[i
]-'a'; if(!son[p][u]) return 0; p=son[p][u]; } return cut[p]; } int main(){ int
n; cin>>n; while(n--){ cin>>op>>str; if(op=="I") insert(str); else cout<<query(
str)<<endl; } }
这就是trie树高效存储的用法。(一定要理解,不要死背,没用)

* 比如再来一道简单的模板题

* 代码 (我们用repeat数组来维护看看这个有没有被点过,当然也可以直接用cut数组 0-0) #include<iostream> #include
<string> #include<cstdio> using namespace std; const int N=1e6+10; int son[N][26
],cut[N],repeat[N],idx; int n,m; void insert(string str){ int p=0; for(int i=0;i
<str.size();i++){ int u=str[i]-'a'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u];
} cut[p]++; } int query(string str){ int p=0; for(int i=0;i<str.size();i++){ int
u=str[i]-'a'; if(!son[p][u]) return 0; p=son[p][u]; } return p; } int main(){
cin>>n; while(n--){ string str; cin>>str; insert(str); } cin>>m; while(m--){
string str; cin>>str; if(!query(str)) puts("WRONG"); else if(cut[query(str)]&&!
repeat[query(str)]++) puts("OK"); else puts("REPEAT"); } }
对于初学者肯定有很多的疑惑,比如怎么维护大小写和字母
用具体题目说话(一般可以直接开到58,就不需要特判,如果有数字就进行特判)

* 代码(归并排序算逆序对+trie树储存+cut数组记录位置) // trie 树+归并排序 #include<iostream> #include
<string> using namespace std; const int N=5e5+10; int son[N][58],cut[N],idx; int
n,a[N],b[N]; long long res=0; void insert(string str,int k){ int p=1; for(int i
=0;i<str.size();i++){ int u=str[i]-'A'; if(!son[p][u]) son[p][u]=++idx; p=son[p]
[u]; } cut[p]=k; } void query(string str,int k){ int p=1; for(int i=0;i<str.size
();i++){ int u=str[i]-'A'; p=son[p][u]; } a[k]=cut[p]; } void merge_sort(int l,
int r){ if(l>=r) return ; int mid=l+r>>1; merge_sort(l,mid),merge_sort(mid+1,r);
int k=0,i=l,j=mid+1; while(i<=mid&&j<=r) if(a[i]<=a[j]) b[k++]=a[i++]; else b[k
++]=a[j++],res+=mid-i+1; while(i<=mid) b[k++]=a[i++]; while(j<=r) b[k++]=a[j++];
for(i=l,j=0;i<=r;i++,j++) a[i]=b[j]; } int main(){ cin>>n; for(int i=1;i<=n;i++)
{ string str; cin>>str; insert(str,i); } for(int i=1;i<=n;i++){ string str; cin
>>str; query(str,i); } merge_sort(1,n); cout<<res; return 0; }
来一道求前缀和的题

* 代码(能力是不断的刷题,来提高的)
我们用cut数组来判断是否满足前缀
(提醒寻找时是 啊a.size()-1,不是a.size())
#include<iostream> #include<cstring> #include<string> using namespace std;
const int N=1e5+10; int son[N][10],cut[N],idx; string str[N]; int T; void init()
{ memset(son,0,sizeof(son)); memset(cut,0,sizeof(cut)); idx=0; } void insert(
string a){ int p=0; for(int i=0;i<a.size();i++){ int u=a[i]-'0'; if(!son[p][u])
son[p][u]=++idx; p=son[p][u]; } cut[p]++; } bool find(string a){ int p=0; for(
int i=0;i<a.size()-1;i++){ int u=a[i]-'0'; p=son[p][u]; if(cut[p]) return true;
} return false; } int main(){ cin>>T; while(T--){ init(); int n; cin>>n; for(int
i=0;i<n;i++) cin>>str[i],insert(str[i]); bool flag=false; for(int i=0;i<n;i++)
if(find(str[i])){ flag=true; break; } if(flag) puts("NO"); else puts("YES"); }
return 0; }
最后来一道后缀题

当然这题很简单N的范围只有200,但是N范围变大时,tried树依旧可以解决 (主要是找不到题)
#include<iostream> #include<cstring> #include<string> #include<algorithm>
using namespace std; const int N=1e5+10; int son[N][59],cut[N],idx; int n,len;
void init(){ memset(son,0,sizeof(son)); memset(cut,0,sizeof(cut)); idx=0; len=0;
} void insert(string a){ int p=0; for(int i=a.size()-1;i>=0;i--){ int u=a[i]-'A'
; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; cut[p]++; } } int query(string a)
{ int p=0; for(int i=a.size()-1;i>=0;i--){ int u=a[i]-'A'; p=son[p][u]; if(cut[p
]==n) len++; else break; } return len; } int main(){ while(cin>>n,n){ init();
string a,b; cin>>b;insert(b); for(int i=1;i<n;i++){ cin>>a;insert(a); if(a.size(
)<b.size()) b=a; } cout<<b.substr(b.size()-query(b))<<endl; } return 0; }
题目是代码修炼的核心,希望大家一起加油
萌新致敬ORZ ,点个赞呗(找题目,很辛苦的)
异或对学会了来补充,各位莫怪,能力有限,萌新磕头。

技术
©2019-2020 Toolsou All rights reserved,
Element-Ui组件 Message 消息提示, alert 弹窗Java:案例理解-接口回调element-ui踩坑记录【Golang 基础系列十】Go 语言 条件语句之if使用css样式设计一个简单的html登陆界面2020顺丰前端暑期实习面经(已过)无孔化就是手机的未来?还有很多问题需要解决【C#】实现学生成绩信息管理系统云原生应用如何做到低成本获得高稳定?用HTML+CSS做一个漂亮简单的个人网页