前言

前綴樹，又稱字典樹，Trie樹，是一種方便查找前綴信息的數據結構。

一、字典樹的實現

1.類描述實現

#include <bits/stdc++.h>
using namespace std;class TrieNode
{
public:int pass=0;int end=0;TrieNode* nexts[26]={NULL};
};TrieNode* root=NULL;void insert(string word)
{TrieNode* node=root;node->pass++;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(node->nexts[path]==NULL){node->nexts[path]=new TrieNode();}node=node->nexts[path];node->pass++;}node->end++;
}int search(string word)
{TrieNode* node=root;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(node->nexts[path]==NULL){return 0;}node=node->nexts[path];}return node->end;
}int prefixNumber(string word)
{TrieNode* node=root;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(node->nexts[path]==NULL){return 0;}node=node->nexts[path];}return node->pass;
}void deleteWord(string word)
{if(search(word)>0){TrieNode* node=root;node->pass--;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(--node->nexts[path]->pass==0){node->nexts[path]=NULL;return ;}node=node->nexts[path];}node->end--;}
}int main()
{int m;cin>>m;root=new TrieNode();int op;string word;for(int i=0;i<m;i++){cin>>op;cin>>word;if(op==1){insert(word);}else if(op==2){deleteWord(word);}else if(op==3){cout<<(search(word)?"YES":"NO")<<endl;}else if(op==4){cout<<prefixNumber(word)<<endl;;}}
}

類描述的方法不推薦，重點是靜態數組的實現方法。

2.靜態數組實現

#include <bits/stdc++.h>
using namespace std;const int MAXN=150001;int trie[MAXN][26];
int treePass[MAXN]={0};
int treeEnd[MAXN]={0};
int cnt=1;//節點數void insert(string word)
{int cur=1;//節點編號treePass[cur]++;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){trie[cur][path]=++cnt;}cur=trie[cur][path];treePass[cur]++;}treeEnd[cur]++;
}int search(string word)
{int cur=1;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){return 0;}cur=trie[cur][path];}return treeEnd[cur];
}int prefixNumber(string word)
{int cur=1;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){return 0;}cur=trie[cur][path];}return treePass[cur];
}void deleteWord(string word)
{if(search(word)>0){int cur=1;treePass[cur]--;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(--treePass[ trie[cur][path] ]==0){trie[cur][path]=0;return ;}cur=trie[cur][path];}treeEnd[cur]--;}
}int main()
{int m;cin>>m;int op;string word;for(int i=0;i<m;i++){cin>>op;cin>>word;if(op==1){insert(word);}else if(op==2){deleteWord(word);}else if(op==3){cout<<(search(word)?"YES":"NO")<<endl;}else if(op==4){cout<<prefixNumber(word)<<endl;;}}
}

首先說明前綴樹的原理，每個節點有pass和end兩個信息，同時還有指向下一個節點的指針，節點與節點間的路徑表示每個字符。所以，在樹往下扎到底的過程中，沿途路徑經過的字符就組成了一個字符串，其中pass的數值表示的是有幾個字符串經過這個節點，end表示的是有幾個字符串在這個節點結束。如“aab”和“abc”，二者首先經過公共節點“a”，然后出現分支“a”和“b”，所以第一個“a”的pass=2，第二個“a”的pass=1，最后一個“b”的end=1，第二個“b”的pass=1，end=0。

首先，設置全局變量，trie數組的一維表示節點的編號，二維表示每條分支去往的下個節點的編號。因為字母只有26個，所以準備26大小即可。之后，設置cnt為節點個數，從1開始。

函數部分，首先是insert函數，用來插入字符串。首先，cur表示當前節點的編號，開始為1，然后先讓pass++。之后遍歷word字符串，每次取出當前字符作為path，若trie[cur][path]==0，即沒有后續節點，那就讓其等于++cnt，建出節點。之后讓cur跳到下個節點，然后pass++。最后，讓end++。

之后是search函數，用來搜索字符串個數。基本思路和insert差不多，只是若trie等于0，即沒有后續節點，說明不存在這個字符串，就返回0；否則最后返回end，即字符串數量。

重點是prefixNumber函數，用來搜索以某個字符串為前綴的串。思路和search差不多，主要區別是最后返回的是pass，即前綴數量。

最后是delete函數，用來刪除字符串。思路就是反向的insert，每次讓pass-1。注意此時的判斷，若下一個節點的pass-1后等于0，即后續節點被刪沒了，直接讓trie等于0后結束即可。

二、前綴樹相關題目

1.接頭密匙

class Solution {
public:#define MAXN 100int trie[MAXN][12];int pass[MAXN]={0};int end[MAXN]={0};int cnt=1;void insert(string word){int cur=1;pass[cur]++;for(int i=0,path;i<word.length();i++){path=word[i]=='-'?10:(word[i]=='#'?11:word[i]-'0');if(trie[cur][path]==0){trie[cur][path]=++cnt;}cur=trie[cur][path];pass[cur]++;}end[cur]++;}int prefixNumber(string word){int cur=1;for(int i=0,path;i<word.length();i++){path=word[i]=='-'?10:(word[i]=='#'?11:word[i]-'0');if(trie[cur][path]==0){return 0;}cur=trie[cur][path];}return pass[cur];}vector<int> countConsistentKeys(vector<vector<int> >& b, vector<vector<int> >& a){for(int i=0;i<a.size();i++){string cur;for(int j=1;j<a[i].size();j++){cur+=a[i][j]-a[i][j-1]+'0';cur+='#';}insert(cur);}vector<int>ans(b.size(),0);for(int i=0;i<b.size();i++){string word;for(int j=1;j<b[i].size();j++){word+=b[i][j]-b[i][j-1]+'0';word+='#';}ans[i]=prefixNumber(word);}        return ans;}
};

?這個題的重點是你得看出來這個情境是求前綴。（捂臉）

之后轉化一下，把數組里每個數的差變成字符串，兩個數之間用“#”間隔，加上負號，trie一共開12大小即可。之后先把a數組insert進去，再根據b數組一個一個找就行。

2.數組中兩個數的最大異或值

class Solution {
public:#define MAXN 3000001int trie[MAXN][2];int cnt=1;int high;void insert(int n){int cur=1;for(int i=high,status;i>=0;i--){status=1&(n>>i);if(trie[cur][status]==0){trie[cur][status]=++cnt;}cur=trie[cur][status];}}int maxXOR(int n){int ans=0;int cur=1;for(int i=high,status,want;i>=0;i--){status=1&(n>>i);want=status^1;if(trie[cur][want]==0){want^=1;}ans|=(status^want)<<i;cur=trie[cur][want];}return ans;}int findMaximumXOR(vector<int>& nums) {int mx=INT_MIN;for(int i=0;i<nums.size();i++){mx=max(mx,nums[i]);}//找最大值的前導1的位置for(int i=31;i>=0;i--){if( (mx&(1<<i) )!=0){high=i;break;}}for(int i=0;i<nums.size();i++){insert(nums[i]);}int ans=0;for(int i=0;i<nums.size();i++){ans=max(ans,maxXOR(nums[i]));}return ans;}
};

?這個題就需要一點思考了。首先思考要達成異或和最大，最好的辦法肯定是選二進制中第一個1最靠前的數，即最大的數。之后，要想異或和最大，理想情況就是找每一位都與最大的數不同的數，這樣異或起來每一位就都是1了。

所以，首先把最大值抓出來，接著為了加速，可以把最大值的前導1的數位取出來，這樣后續從這個位置開始找即可，不需要從31位開始。再把每個數的二進制形式insert進去，由于只有0和1兩種狀態，所以trie的大小為2即可。

重點就是maxXOR函數，首先每次讓status為n第i位上的狀態。注意，這里由于trie只有0和1兩條分支，所以選擇讓n>>i的方法。然后，最優選擇肯定是找status不同的狀態，所以want=status^1，若沒有找到，就再^1回到原狀態。最后把這一位的異或結果或進ans里即可。

這個題說實話還是有點難度的。

3.單詞搜索 II

class Solution {
public:#define MAXN 10001int trie[MAXN][26];int pass[MAXN]={0};string end[MAXN];int cnt=1;void insert(string word){int cur=1;pass[cur]++;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){trie[cur][path]=++cnt;}cur=trie[cur][path];pass[cur]++;}end[cur]=word;}int prefix(string word){int cur=1;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){return 0;}cur=trie[cur][path];}return pass[cur];}//返回值為找到的字符串個數int dfs(vector<vector<char>>&board,int i,int j,int t,vector<string>&ans){if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]==0){return 0;}int tmp=board[i][j];int path=tmp-'a';t=trie[t][path];if(pass[t]==0||t==0)//找過了或沒有{return 0;}int num=0;if(end[t]!="")//找到一個{num++;ans.push_back(end[t]);end[t]="";}board[i][j]=0;num+=dfs(board,i+1,j,t,ans);num+=dfs(board,i-1,j,t,ans);num+=dfs(board,i,j+1,t,ans);num+=dfs(board,i,j-1,t,ans);pass[t]-=num;//找完一個就刪除board[i][j]=tmp;return num;}vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {vector<string>ans;for(int i=0;i<words.size();i++){insert(words[i]);}for(int i=0;i<board.size();i++){for(int j=0;j<board[i].size();j++){dfs(board,i,j,1,ans);}}return ans;}
};

?這個題就更是群賢畢至，不僅有前綴樹，還有帶路徑的遞歸和還原現場。

前綴樹在這個題的作用就是剪枝，而且有三次剪枝。首先，通過前綴樹，可以讓每次遞歸去往的都是有效的格子。其次，這里讓end數組直接存放整個字符串，可以方便遞歸結束時直接收集結果。最后，每次在找完一個字符串后就把節點刪除，也可以減少不必要的搜索。

重點就是這個dfs函數，首先若越界了或走到走過的格子就返回0。之后取當前格子上的字符和path，t表示前綴樹當前節點的編號，所以讓t去下一個節點，若下一個節點找過了或者沒有就返回0。然后若end有東西，說明找到了，就記錄答案之后刪除。接著分別去四個方向遞歸，注意這里在回來時不僅要把格子還原，還有讓pass減去找到的數量，即刪去找過的字符串，所以要讓dfs函數帶上返回值，表示找到的字符串個數。

有一說一這個題確實難。

總結

前綴樹還是很強的，用好了能很大程度優化算法。

END