<>trie tree （ Usage and summary ）

- Nanchang science and technology training team

*
What is it trie tree （ Find a picture ）

- This is trie The basic principle of tree storage .

That is to store each character in a tree , And save the node , To find out .
This is very efficient （ It can be seen that , Because the character reuse rate is very high ）

- trie The role of trees

1 Store and find characters （ It's very efficient , The most basic usage ）
2 Find whether the suffix before two characters satisfies the string （ Very important , It's also the core usage ）
3 How many prefixes or suffixes are the same before and after a suffix
4 XOR pair （ hard , I haven't learned yet , Don't ask , The question is that I.Q. is too low (;′⌒`) ）
qwq I must be wondering why not KMP Dafa .（0.0）
（ Of course, it can also be used KMP, But when the number is large, it's very slow , To enumerate one by one , Sorry ）

- Template supply

Here's the big part , How to use code to realize ?

*
The first is storage （ insert trie tree ）
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] ++ ; }
* the second Find character // Query string 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]; }
These are the two main ways to play , The rest are to maintain themselves trie tree .

* A template question

#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; } }
This is it. trie The usage of tree efficient storage .（ You have to understand , Don't give up , useless ）

* For example, another simple template problem

* code （ We use repeat Array to maintain, see if this has been clicked , Of course, it can also be used directly cut array 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"); } }
There must be a lot of doubts for beginners , For example, how to maintain case and letter
Talk about specific topics （ Generally, you can drive directly to 58, You don't need a special judgment , If there are numbers, make a special judgment ）

* code （ Merge sort to calculate reverse order pair +trie Tree storage +cut Array record location ） // trie tree + Merge sort #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; }
A problem of finding the sum of prefixes

* code （ Ability is a constant brush , To improve ）
We use cut Array to determine whether the prefix is satisfied
（ Remind when looking for ah a.size()-1, no 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; }
Finally, a suffix problem

Of course, the question is very simple N The scope of the project is only 200, however N When the range becomes larger ,tried Trees can still solve the problem （ The main problem is that we can't find it ）
#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; }
Title is the core of code cultivation , I hope you can come on together
Adorable new ORZ , Like it （ Find a topic , It's hard work ）
XOR to learn to complement , No wonder , Limited capacity , Mengxin kowtow .

Technology
Daily Recommendation