Description：

给 $n$ 个字符串求一个最短的字典序最小的串 $T$ 使得所有给出的字符串都是 $T$ 的子串。

$1\le n \le 12$

Solution：

多个串差不多就是 $AC$ 自动机了，先把 $AC$ 自动机建出来， $n\le 10$ 可以在每个点把这个点能代表的串压成一个状态，注意求 $fail$ 时要把 $state$ 或起来，然后直接 $BFS$ 求 $state=(1<<n)-1$ 的字典序最小解就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n;

#define MAXN 13

#define MAXL 60

struct node

{

	int c[26];

	int fail;

	int state;

	node(){memset(c,0,sizeof(c));state = 0;}

}t[MAXN * MAXL * MAXN];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

string s[MAXN];

void insert(int k)

{

	int cur = root,l = s[k].length();

	for(int i = 0;i < l;++i)

	{

		if(t[cur].c[s[k][i] - 'A'] == 0)t[cur].c[s[k][i] - 'A'] = newnode();

		cur = t[cur].c[s[k][i] - 'A'];

	}

	t[cur].state |= (1 << (k - 1));

	return;

}

void makefail()

{

	queue<int> q;

	for(int i = 0;i < 26;++i)

	{

		if(t[root].c[i] != 0)

		{

			t[t[root].c[i]].fail = root;

			q.push(t[root].c[i]);

		}

	}

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = 0;i < 26;++i)

		{

			if(t[k].c[i] != 0)

			{

				int p = t[k].fail;

				while(p && t[p].c[i] == 0)p = t[p].fail;

				t[t[k].c[i]].fail = t[p].c[i];

				t[t[k].c[i]].state |= t[t[p].c[i]].state;

				q.push(t[k].c[i]);

			}

			else

			{

				t[k].c[i] = t[t[k].fail].c[i];

			}

		}

	}

	return;

}

struct state

{

	int id,sta,pla;

};

int cnt = 0;

int fa[2500000],a[2500000];

bool vis[MAXN * MAXL * MAXN][1 << MAXN];

void pt(int id)

{

	if(id == 1)return;

	pt(fa[id]);

	putchar(a[id] + 'A');

	return;

}

void solve()

{

	cnt = 0;

	queue<state> q;

	++cnt;

	q.push((state){cnt,0,root});

	vis[root][0] = true;

	while(!q.empty())

	{

		state k = q.front();q.pop();

		if(k.sta == (1 << n) - 1)

		{

			pt(k.id);

			return;

		}

		for(int i = 0;i < 26;++i)

		{

			if(t[k.pla].c[i] == 0)continue;

			if(vis[t[k.pla].c[i]][k.sta | t[t[k.pla].c[i]].state])continue;

			vis[t[k.pla].c[i]][k.sta | t[t[k.pla].c[i]].state] = true;

			++cnt;

			fa[cnt] = k.id;a[cnt] = i;

			q.push((state){cnt,(k.sta | t[t[k.pla].c[i]].state),t[k.pla].c[i]});

		}

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		cin >> s[i];

		insert(i);

	}

	makefail();

	solve();

	return 0;

}