C++11(clang++ 3.9) 解法, 执行用时: 211ms, 内存消耗: 20568K, 提交时间: 2019-07-26 20:45:50

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 521
int tr[26][N],ed[N],tot,fail[N],n;
void insert(char a[],int pos){
	int i,now=0;
	for(i=0;a[i];i++){
		int x=a[i]-'A';
		if(!tr[x][now])tr[x][now]=++tot;
		now=tr[x][now];
	}
	ed[now]|=(1<<pos);
}
void build(){
	int i;
	queue<int>Q;
	for(i=0;i<26;i++)if(tr[i][0])Q.push(tr[i][0]);
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(i=0;i<26;i++){
			if(tr[i][x])fail[tr[i][x]]=tr[i][fail[x]],ed[tr[i][x]]|=ed[fail[tr[i][x]]],Q.push(tr[i][x]);
			else tr[i][x]=tr[i][fail[x]];
		}
	}
}
struct TP{
	int num,st,pos;
};
int vis[N][1<<13],path[N*(1<<13)],letter[N*(1<<13)];
char ans[N*N*N];
char a[N];
int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%s",a);
		insert(a,i);
	}
	build();
	queue<TP>Q;
	Q.push((TP){0,ed[0],0});
	vis[0][ed[0]]=1;
	int last=0,tot=0;
	while(!Q.empty()){
		int num=Q.front().num,st=Q.front().st,pos=Q.front().pos;Q.pop();
		if(st==(1<<n)-1){
			while(last){
				ans[--num]='A'+letter[last];
				last=path[last];
			}
			printf("%s",ans);
			break;
		}
		for(i=0;i<26;i++){
			int nxt=tr[i][pos],nst=st|ed[nxt];
			if(vis[nxt][nst])continue;
			vis[nxt][nst]=1;
			path[++tot]=last;
			letter[tot]=i;
			Q.push((TP){num+1,nst,nxt});
		}
		last++;
	}
	return 0;
}