frank15 @ 2021-04-17 17:09:13
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#define bug puts("----------");
using namespace std;
const int maxn=25005;
int n;
int cnt;
string a,ans;
struct t{
int nex[30];
bool visit;
int num,SIZE;
}tree[maxn];
vector<int> v[maxn];
void qinsert(string s){
int p=0;
for(int i=0;i<s.size();i++){
int c=s[i]-'a';
if(!tree[p].nex[c])
tree[p].nex[c]=++cnt;
p=tree[p].nex[c];
tree[p].num=c;
}
tree[p].visit=1;
}
void build(int node){
for(int i=0;i<26;i++)
if(tree[node].nex[i]){
v[node].push_back(tree[node].nex[i]);
build(tree[node].nex[i]);
}
}
bool cmp(int X,int Y){
return tree[X].SIZE<tree[Y].SIZE;
}
void dfs(int node){
tree[node].SIZE++;
for(int i=0;i<v[node].size();i++){
dfs(v[node][i]);
// cout<<node<<' '<<v[node][i]<<' '<<tree[v[node][i]].SIZE<<' '<<tree[node].SIZE<<endl;
// cout<<tree[node].SIZE<<' '<<tree[v[node][i]].SIZE<<endl;
tree[node].SIZE+=tree[v[node][i]].SIZE;
// cout<<tree[node].SIZE<<' '<<tree[v[node][i]].SIZE<<endl;
// cout<<node<<' '<<v[node][i]<<' '<<tree[v[node][i]].SIZE<<' '<<tree[node].SIZE<<endl;
}
sort(v[node].begin(),v[node].end(),cmp);
}
void dfs2(int node,int fa){
ans+=char(tree[node].num+'a');
if(tree[node].visit)
ans+='P';
for(int i=0;i<v[node].size();i++){
dfs2(v[node][i],node);
ans+='-';
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>a;
qinsert(a);
}
build(0);
dfs(0);
// for(int i=0;i<=cnt;i++){
// cout<<i<<endl;
// for(int j=0;j<v[i].size();j++)
// cout<<v[i][j]<<' ';
// cout<<endl;
// }
dfs2(0,0);
int len=ans.size()-1;
while(ans[len]=='-')
len--;
cout<<len<<endl;
for(int i=1;i<len;i++)
cout<<char(ans[i])<<endl;
}
by 数学小王子 @ 2021-04-17 17:17:13
orz切紫题的巨佬
by JJA_ @ 2021-04-17 17:48:14
@数学小王子 请紫衫
by 0142_Zssd @ 2022-01-03 15:10:39
emmmm...