【算法每日一练]-结构优化（保姆级教程 篇8 字典树，后缀数组，基数排序）

目录

? 字典树

基数排序

后缀数组?

---

? ? ? ?

????????

? 字典树

又称Trie树、单词查找树、前缀树，是一种树形结构，用于保存关联数组，其中的键通常是字符串。适合统计、 排序和存储大量的字符串，经常被搜索引擎系统用于文本词频统计。

字典树利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

????????

字典树的3个性质：

1，根节点不包含字符，除了根节点外每一个节点都只包含一个字符。

2，从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。

3，每个节点的所有子节点包含的字符都不相同(因为会共用前缀)

????????

例如，这里有单词bee，beer，bin，bike，yes。然后如图建树，然后在每个单词结束的位置都加一个end[]标记，表示从根到这里有一个单词就行了

创建过程：就是将字符串插入到字典树的过程，如果有这个分支就直接使用(公用前缀)，如果没有那就创建这个分支点。

注意：每个分支点一定是26个大小，每个位置表示不同的字符。每个位置里面存的是下一个节点的下标，以便查找时候快速遍历。?

参考代码：?

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005,maxz=26;//节点数
int trie[maxn][maxz];//里面存放下一个节点的下标
string word[maxn];//翻译的单词
int val[maxn];//值的下标
bool en[maxn];//单词结束标记
int n,tot;

void insert(string s,int k){//插入字符串s，下标为k
	int len=s.size(),p=1;
	for(int i=0;i<len;i++){
		int ch=s[i]-'a';//转数字
		if(!trie[p][ch]) trie[p][ch]=++tot;//不存在创建，同时记录下一个节点下标
		p=trie[p][ch];//指向下一个
	}
	val[p]=k;//记录下标，到时候直接返回k再传给word[]即可
	en[p]=1;//如果单词和翻译是一一对应的，那么就完全可以在end中直接存入下标（比如此题）
}

int search(string s){//在字典树中查该单词是否存在
	int len=s.size(),p=1;
	for(int i=0;i<len;i++){
		p=trie[p][s[i]-'a'];
		if(!p) return 0;
	}
	if(en[p])return val[p];//返回下标
	return 0;
}

int main(){
	string s,s1;
	tot=1;
	int i=1;
	while(getline(cin,s)){
		if(!s.size())break;
		int j=s.find(' ');
		word[i]=s.substr(0,j);
		s1=s.substr(j+1);
		insert(s1,i);
		i++;
	}
	while(cin>>s){
		int k=search(s);
		if(k)cout<<word[k]<<'\n';
		else cout<<"eh"<<'\n';
	}
}

哈希树的map写法，慢?

#include <bits/stdc++.h>//map写法
using namespace std;
unordered_map<string,string> ma;
int main(){
	string s,s1,s2,str;
	while(getline(cin,s)){
		if(s.empty()) break;
		int pos=s.find(' ');
		s1=s.substr(0,pos);
		s2=s.substr(pos+1);
		ma.insert(make_pair(s2,s1));
	}
	while(cin>>str){
		auto it=ma.find(str);
		if(it!=ma.end()) cout<<ma[str]<<'\n';
		else cout<<"eh"<<'\n';
	}
}

?参考样例：
dog ogday
cat atcay
pig igpay
froot ootfray
loops oppslay
????????

????????

基数排序

#include <bits/stdc++.h>//基数排序的桶排序是一种思想：桶是虚的，可以是每个数字的位，也可以是字符串的长度，你真正要的是每次排后的结果
using namespace std;//不能处理负数
const int maxn=10000;
int n,a[maxn],b[10][maxn];

int maxbit(){
	int maxval=a[0],d=0;
	for(int i=1;i<n;i++)  if(a[i]>maxval) maxval=a[i];//找最大元素，然后求位数
	while(maxval!=0){
		d++;
		maxval/=10;
	}
	return d;
}

int bitnum(int x,int bit){//求x在bit位上的数字
	int tmp=1;
	for(int i=1;i<bit;i++) tmp*=10;
	return (x/tmp)%10;
}

void radixsort(){//基数排序
	int i,j,k,bit,maxb;
	maxb=maxbit();//找数组中最大位数
	for(bit=1;bit<=maxb;bit++){
		for(int j=0;j<n;j++){//分配
			int num=bitnum(a[j],bit);//取第bit位上的数字为桶号
			int index=++b[num][0];//更新读出计数器
			b[num][index]=a[j];//放入元素
		}
		for(int i=0,j=0;i<10;i++){//收集，从0号桶开始
			for(int k=1;k<=b[i][0];k++)a[j++]=b[i][k];//更新原数组
			b[i][0]=0;
		}
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	radixsort();//排序
	for(int i=0;i<n;i++)cout<<a[i]<<' ';
	cout<<'\n';
}

#include <bits/stdc++.h>//memcpy(ar,br,sizeof(br))
using namespace std;
const int maxn=10000;
int a[maxn],n;

int maxbit(){
	int d=1,p=10;
	for(int i=0;i<n;i++){
		while(a[i]>=p){
			p*=10;++d;
		}
	}
	return d;
}

void radixsort(){
	int d=maxbit();
	int tmp[maxn],cnt[10];//tmp数组存放每次的结果并给原数组，cnt存放桶中的数量
	int i,j,pos,k=1;
	for(i=1;i<=d;i++){//d次排序
		memset(cnt,0,sizeof(cnt));
		for(j=0;j<n;j++){
			pos=(a[j]/k)%10;//从个位开始(往桶里扔)
			cnt[pos]++;//统计每个桶中的记录数
		}		
		for(j=1;j<10;j++) cnt[j]+=cnt[j-1];//对桶前缀和一下
		
		for(j=n-1;j>=0;j--){//将桶中的记录倒着拿出来给tmp，即排序结果给tmp
			pos=(a[j]/k)%10;//a数组必须是上次的结果
			tmp[--cnt[pos]]=a[j];//前缀和下：计数减一就是下标值！！！
		}
		memcpy(a,tmp,sizeof(tmp));//排序结果传给原数组a
		for(j=0;j<n;j++)cout<<a[j]<<"\t";cout<<'\n';
		k=k*10;//用于获取下一位
	}
}
/*
cnt数组就是桶计数器，用于将每次的排序结果传给排名数组a（原数组），只不过需要借助中间辅助数组tmp
*/
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	radixsort();//排序
	for(int i=0;i<n;i++)cout<<a[i]<<' ';
}





int cmp(int i,int j){
	if(rk[i]!=rk[j])return rk[i]<rk[j];//比较前一半
	int ri=(i+k<=n?rk[i+k]:-1);//后面没有的话补0嘛，可不就排名-1
	int rj=(j+k<=n?rk[j+k]:-1);
	return ri<rj;//比较后一半
}

void getsa(int n,char *str){
	for(int i=1;i<=n;i++){
		sa[i]=i;rk[i]=str[i];//比较码即可
	}
	for(int k=1;k<=n;k*=2){//倍增
		sort(sa+1,sa+1+n,cmp);//先对sa排序
		rk2[sa[1]]=1;//rk2是临时记录rk的数组
		for(int i=2;i<=n;i++)
			rk2[sa[i]]=rk2[sa[i-1]]+cmp(sa[i-1],sa[i]);//rk2可以从前一位推，如果cmp为0，那么rk相等，如果为1表示前一位小于当前位，要加1
		for(int i=1;i<=n;i++)
			rk[i]=rk2[i];//更新rk数组
	}
}

?????????

后缀数组?

#include <bits/stdc++.h>
using namespace std;
const int maxn=100,maxm=10000;
int n;
int ss[maxn],sa[maxn];
int wa[maxn],wb[maxn],wv[maxn],c[maxm];

int cmp(int *r,int a,int b,int l){
	return r[a]==r[b]&&r[a+l]==r[b+l];
}

void print(int *s,int t){
	for(int i=0;i<t;i++)cout<<s[i]<<'\t';
	cout<<'\n';
}

void print_suf(string s,int *sa){
	for(int i=1;i<=n;i++)cout<<s.substr(sa[i])<<'\n';
}

void da(int *r,int *sa,int n,int m){
	int i,k,p,*x=wa,*y=wb;
	
//先用c将基数排序结果给sa
	for(i=0;i<m;i++)c[i]=0;//c数组是每个桶的计数器
	for(i=0;i<n;i++)c[x[i]=r[i]]++;//r传递给x并统计数量
	for(i=1;i<m;i++)c[i]+=c[i-1];//累加
	for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;//到此步：sa就是基数排序结果(2^0长度)，x就是我们设置的对应rank数组
	
	cout<<"rank: \t";
	print(x,n);
	cout<<"sa: \t";
	print(sa,n);
//然后利用上次排序结果x进行第二第一关键字排序可得下一次的排序结果
//首先对x并移位可得第二关键字排序，然后将第二关键字转换成名次即第一关键字，然后第一关键字基数排序 
	for(k=1;k<=n;k<<=1){//倍增（两两结合其实就是第二第一关键字）求出每次的sa和x（rank）
		p=0;//p是名次，用于求sa
		for(i=n-k;i<n;i++) y[p++]=i;//先求第二关键字，补零位置的下标当然在最前面
		for(i=0;i<n;i++) 
		  if(sa[i]>=k) y[p++]=sa[i]-k;//第二关键字排序结果放入y中（移位，小于的不要动）
		cout<<"y: \t";
		print(y,n);
		
		for(i=0;i<n;i++)wv[i]=x[y[i]];//将第二关键字排序结果转成名次即第一关键字wv
//在根据这次的排序结果基数排序求出x
		for(i=0;i<m;i++)c[i]=0;//再次基数排序（对第一关键字）
		for(i=0;i<n;i++)c[wv[i]]++;
		for(i=1;i<m;i++)c[i]+=c[i-1];
		for(i=n-1;i>=0;i--)sa[--c[wv[i]]]=y[i];//到此步：sa是第一关键字的，
		cout<<"x[y[i]]: ";
		print(wv,n);
		cout<<"sa: ";
		print(sa,n);
//求x数组	
		swap(x,y);//交换数组
		p=1;x[sa[0]]=0;
		for(i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++;//sa再转x（也就是rank）
		cout<<"rank: ";
		print(x,n);
		cout<<"sa: ";
		print(sa,n);
		cout<<'\n'<<'\n'<<'\n';
		if(p>=n)break;//名次已经都不相同了，就可以提前结束了
		m=p;//m是桶数（按名次来设置桶，专门处理同名得）
	}	
}

int ran[maxn],hei[maxn];
void calhei(int *r,int *sa,int n){
	int i,j,k=0;
	for(i=1;i<=n;i++)ran[sa[i]]=i;
	print(ran,n);
	for(i=0;i<n;i++){
		if(k) k--;
		j=sa[ran[i]-1];
		while(r[i+k]==r[j+k]) k++;
		hei[ran[i]]=k;
	}
	print(hei+1,n);
}
int main(){
	string s;
	cin>>s;
	n=s.size();
	for(int i=0;i<n;i++)ss[i]=s[i]-'a'+1;//转数字
	ss[n]=0;
	da(ss,sa,n+1,maxm);//构造后缀数组  maxm用于基数排序的最大值
	print_suf(s,sa);
	calhei(ss,sa,n);
}