Luogu P2322 最短母串问题

题目大意

  有(n)个字符串(s_1,s_2,dots,s_n)（(1 leq n leq 12)，(1 leq | s_i | leq 50)），求一个最短的字符串(S)，使这(n)个字符串都是(S)的子串。

 

题解

  我们先对这(n)个字符串建AC自动机，这里我们对于Trie上的结点(i)，定义一个状态(state_i)，表示第(i)个结点对应的字符串，包含的题目中给出的哪些字符串。
  我们可以从Trie上的根节点，按照字典序BFS，我们用(f)表示当前经过的所有结点的包含的所有字符串，显然，当(f)包含所有字符串时，此时即为最优解。具体可以看代码理解，没什么好说的。

#include <iostream>
#include <cstdio>
#include <cstring>

#define MAX_N (12 + 5)
#define MAX_S ((1 << 12) + 5)
#define MAX_LEN (50 + 5)

using namespace std;

struct Trie
{
	int to[30];
	int fail;
	char ch;
	int state;
};

int n;
char s[MAX_LEN];
Trie t[MAX_N * MAX_LEN];
int m = 1;
int q[MAX_N * MAX_LEN], l, r;
bool vis[MAX_N * MAX_LEN][MAX_S];
int pos[MAX_N * MAX_LEN * MAX_S], prev[MAX_N * MAX_LEN * MAX_S], f[MAX_N * MAX_LEN * MAX_S];
char ans[MAX_N * MAX_LEN];
int top;

void Insert(int state)
{
	int len = strlen(s + 1);
	int now = 1, tmp;
	for (int i = 1; i <= len; ++i)
	{
		tmp = s[i] - 'A';
		if (!t[now].to[tmp])
		{
			t[now].to[tmp] = ++m;
			t[m].ch = s[i];
		}
		now = t[now].to[tmp];
	}
	t[now].state |= state;
	return;
}

void Build()
{
	for (int i = 0; i < 26; ++i)
	{
		t[0].to[i] = 1;
	}
	q[1] = 1;
	l = r = 1;
	int now;
	while (l <= r)
	{
		now = q[l++];
		for (int i = 0; i < 26; ++i)
		{
			if (t[now].to[i])
			{
				t[t[now].to[i]].fail = t[t[now].fail].to[i];
				t[t[now].to[i]].state |= t[t[t[now].fail].to[i]].state;
				q[++r] = t[now].to[i];
			}
			else
			{
				t[now].to[i] = t[t[now].fail].to[i];
			}
		}
	}
	return;
}

void Solve()
{
	vis[1][0] = true;
	pos[0] = 1;
	int u, v;
	int now = 0, cnt = 0;
	const int lim = (1 << n) - 1;
	while (now <= cnt)
	{
		if (f[now] == lim)
		{
			while(now)
			{
				u = pos[now];
				if (t[u].ch) ans[++top] = t[u].ch;
				now = prev[now];
			}
			break;
		}
		u = pos[now];
		for (int i = 0; i < 26; ++i)
		{
			v = t[u].to[i];
			if (vis[v][f[now] | t[v].state]) continue;
			vis[v][f[now] | t[v].state] = true;
			pos[++cnt] = v;
			prev[cnt] = now;
			f[cnt] = f[now] | t[v].state;
		}
		++now;
	}
	return;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", s + 1);
		Insert(1 << i - 1);
	}
	Build();
	Solve();
	while (top) putchar(ans[top--]);
	return 0;
}