本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-02 19:31:32

怎么没人写字典树？我来补一篇。

发现要使字符串序列字符串序列最小，则对于两个相邻的字符串 $s_i$，$s_j$，$s_{i,k}\le s_{j,k}$，不难发现用字典树倒序插入是好维护的，只需在字典树上每遍历到一个节点，判断是否本节点下一层已存在比当前字符字典序更小的字符即可。

发现难以处理字符串长度不一的情况，这时我们只需标记字符串结尾为一个独立节点，使其小于所有字符，每次额外判断即可。

复杂度 $O(n\times26)$，$n$ 为字符串总长度。

#include<bits\/stdc++.h>
#define endl '\n'
using namespace std;
const int N=5e5+10;
int t[N][30];
int cnt;
string ans[N];
void ins(string s,int xx){
	int u=0;
	int w=-1;
	for(int i=0;i<s.size()-1;i++){
		int x=s[i]-'a'+1;
		bool mx=0;
		for(int j=x-1;j>=0;j--){
			if(t[u][j]){
				mx=1;break; 
			}
		}
		if(mx){
			break;
		}
		if(!t[u][x]){
			t[u][x]=++cnt;
		}
		u=t[u][x];
		w=i;
	}
	t[u][0]=++cnt;
	ans[xx]='#';
	for(int i=0;i<=w;i++){
		ans[xx]+=s[i];
	}
} 
string S[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		for(int i=0;i<s.size();i++){
			s[i]=s[i+1];
		}
		S[i]=s;
	}
	for(int i=n;i>=1;i--){
		ins(S[i],i);
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}