chenxia25 @ 2019-08-29 10:59:41
RT,Trie,跟题解一样的方法,但玄学RE3个点,求助!
提交记录:https://www.luogu.org/record/23447567
代码:
#include<bits/stdc++.h>
using namespace std;
#define ppb pop_back()
#define pb push_back
const int N=25000,LEN=20,LET=26;
int n;
char a[LEN+5];
int mx;
vector<int> las;
string ans;
struct trie{
int sz;
struct node{bool ed,las;int son[LET];}nd[N*LEN+2];
#define ed(p) nd[p].ed
#define las(p) nd[p].las
#define son(p) nd[p].son
int nwnd(){
ed(++sz)=false;
las(++sz)=false;
memset(son(sz),0,sizeof(son(sz)));
return sz;
}
void init(){nwnd();}
void insert(char str[]){
int len=strlen(str+1),p=1;
if(len>mx)while(las.size())las(las.back())=false,las.ppb;
for(int i=1;i<=len;i++){
if(!son(p)[str[i]-'a'])son(p)[str[i]-'a']=nwnd();
p=son(p)[str[i]-'a'];
if(len>mx)las(p)=true,las.pb(p);
}
ed(p)=true;
mx=max(mx,len);
}
void dfs(int x=1){
if(ed(x))ans+='P';
for(int i=0;i<26;i++){
int y=son(x)[i];
if(las(y))continue;
if(y)ans+='a'+i,dfs(y),ans+='-';
}
for(int i=0;i<26;i++){
int y=son(x)[i];
if(!las(y))continue;
if(y)ans+='a'+i,dfs(y),ans+='-';
}
}
}tri;
int main(){
tri.init();
cin>>n;
for(int i=1;i<=n;i++)cin>>a+1,tri.insert(a);
tri.dfs();
int len=ans.size();
while(len&&ans[len-1]=='-')len--;
cout<<len<<"\n";
for(int i=0;i<len;i++)cout<<ans[i]<<"\n";
return 0;
}
by chenxia25 @ 2019-08-29 11:03:46
哦我懂了,拜拜,此帖终
by 7k1danWhen @ 2022-05-22 10:26:13
@chenxia25 dalao我也RE了三个点,能帮忙看一下吗?link
by 7k1danWhen @ 2022-05-22 10:34:59
@chenxia25 不用了,已会