Trie

定義

字典樹，英文名 trie。顧名思義，就是一個像字典一樣的樹。

引入

這棵樹包含了：

aa
aba
ba
caaa
cab
cba
ac

這幾個單詞。

如何維護

定義 son[i][j] 為在 i 號節點，往下邊權為 j 的下一個節點。

struct trie {
	int son[100000][26],cnt;
	int back[100000];
	void insert(string s) {  // 插入字符串
		int p=0;
		for (int i=0;i<s.size();i++) {
			int c=s[i]-'a';
			if (!son[p][c]) son[p][c]=++cnt;
			p=son[p][c];
		}
		back[p]++;
	}
	bool find(string s) {  // 查找字符串
		int p=0;
		for (int i=0;i<s.size();i++) {
			int c=s[i]-'a';
			if (!son[p][c]) return 0;
			p=son[p][c];
		}
		return back[p];
	}
};

應用

應用于字符長度不長，但數量極多的情況。

1. 字符串的前綴數量。

記錄下沿途的 back 總和，就是答案。

struct trie {
	int son[100000][26],cnt;
	int back[100000];
	void insert(string s) {  // 插入字符串
		int p=0;
		for (int i=0;i<s.size();i++) {
			int c=s[i]-'a';
			if (!son[p][c]) son[p][c]=++cnt;  // 如果沒有，就添加結點
			p=son[p][c];
		}
		back[p]++;
	}
	bool find(string s) {  // 查找字符串前綴數量
		int p=0;
		int ans=0;
		for (int i=0;i<s.size();i++) {
			int c=s[i]-'a';
			if (!son[p][c]) return ans;
			p=son[p][c];
			ans=ans+back[p];
		}
		return ans;
	}
};

2. 01字符串

如果是關于二進制，便可以直接轉換為二進制。

例題:

給定 N 個整數 \(A_1,A_2,A_3,···,A_n\) 中選出兩個進行異或計算，得到的結果最大是多少？

我們可以先枚舉其中一個數，從高位開始，每一次如果能異或后得到一，便優先選擇，最終取 n 個方案的最大值。

CODE:

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~優美的分界線~~*&^%$#@!*&^%$#@!*/
const int N=100005;
int n,A[N];
int tot,ch[N*32][2];
/*!@#$%^&*!@#$%^&*~~優美的分界線~~*&^%$#@!*&^%$#@!*/
void ins(int x) {
	int p=0;
	for(int i=30;i>=0;i--) {
		int j=(x>>i)&1;
		if(ch[p][j]==0) ch[p][j]=++tot;
		p=ch[p][j];
	}
}
int find(int x){
	int p=0,ans=0;
	for(int i=30;i>=0;i--) {
		int j=(x>>i)&1;
		int k=j?0:1;
		if(ch[p][k]==0) p=ch[p][j];
		else p=ch[p][k],ans+=(1<<i);
	}
	return ans;
}
/*!@#$%^&*!@#$%^&*~~優美的分界線~~*&^%$#@!*&^%$#@!*/
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>A[i];
		ins(A[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,find(A[i]));
	cout<<ans;
	return 0;
}