https://www.luogu.com.cn/record/141668600

注意 Trie 每个点包含的状态记得或上 fail 的状态。我下面的代码要加上第 28 行才能 AC。

#include<bits/stdc++.h>
using namespace std;

const int N = 610;

int t[N][26], idx = 1, fail[N], c[N], v[N][1<<12], f1[N][1<<12], f2[N][1<<12];
queue<int>q1, q2;
char str[N], ans[N];int top;
void ins(int id)
{
	int i, p = 1, l;
	cin>>str+1, l = strlen(str+1);
	for(i=1;i<=l;i++)
	{
		if(!t[p][str[i]-'A']) t[p][str[i]-'A'] = ++idx;
		p = t[p][str[i]-'A'];
	}
	c[p] |= id;
}
void build()
{
	int i;
	for(i=0;i<26;i++) t[0][i] = 1;fail[1] = 0;
	queue<int>q;q.push(1);
	while(!q.empty())
	{
		int d = q.front();q.pop();
		c[d] |= c[fail[d]];//这句话很重要！
		for(i=0;i<26;i++)
			if(t[d][i]) fail[t[d][i]] = t[fail[d]][i], q.push(t[d][i]);
			else t[d][i] = t[fail[d]][i];
	}
}

int main()
{
	int n, i;
	cin>>n;
	for(i=1;i<=n;i++) ins(1<<i-1);
	build();
	q1.push(1), q2.push(0);
	v[1][0] = 1;
	while(!q1.empty())
	{
		int d1 = q1.front(), d2 = q2.front();q1.pop();q2.pop();
		if(d2==((1<<n)-1))
		{
			while(d1!=1||d2!=0)
			{
				ans[++top] = v[d1][d2];
				int e1 = f1[d1][d2], e2 = f2[d1][d2];
				d1 = e1, d2 = e2;
			}
			while(top) cout<<ans[top--];
			break;
		}
		for(i=0;i<26;i++)
		{
			int e1 = t[d1][i];int e2 = d2 | c[e1];
			if(v[e1][e2]) continue;
			v[e1][e2] = i + 'A';
			f1[e1][e2] = d1, f2[e1][e2] = d2;
			q1.push(e1), q2.push(e2);
		}
	}
	return 0;
}