```cpp
#include <bits/stdc++.h>
#define lowb(a, r, x) lower_bound(a + 1, a + r + 1, x) - a
#define uppb(a, r, x) upper_bound(a + 1, a + r + 1, x) - a
#define _for(i, a, b) for (ll i = a; i <= b; ++i)
#define for_(i, a, b) for (ll i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
#define NO nullptr
typedef long double ldb;
typedef long long ll;
typedef double db;
const int N = 610, M = 1 << 12;
namespace ACAUTOMATON {
class ACAutomaton {
private:
int cnt = 0, nxt[N][26], fail[N], end[N];
int t = 0, vis[N][M], la[N][M], ch[N][M], lst[N][M];
public:
inline void Insert (char* s, int id) {
int p = 0, len = strlen (s + 1);
// puts (s + 1);
_for (i, 1, len) {
int c = s[i] - 'A';
if (!nxt[p][c]) nxt[p][c] = ++cnt;
p = nxt[p][c];
// printf ("%d ", p);
}
// puts ("");
end[p] |= 1 << (id - 1);
return;
}
inline void Build () {
std::queue <int> q;
_for (i, 0, 25) if (nxt[0][i]) fail[nxt[0][i]] = 0, q.push (nxt[0][i]);
while (!q.empty ()) {
int u = q.front (); q.pop ();
_for (i, 0, 25) {
if (nxt[u][i]) fail[nxt[u][i]] = nxt[fail[u]][i], end[nxt[u][i]] |= end[u], q.push (nxt[u][i]);
else nxt[u][i] = nxt[fail[u]][i];
}
}
// _for (i, 1, cnt) printf ("%lld %lld\n", i, end[i]);
// puts ("");
// printf ("!!:%lld\n", nxt[4]['P' - 'A']);
return;
}
inline int BFS (int num, int ST) {
memset (vis, 0x3f, sizeof (vis));
std::queue <std::pair <int, int> > q;
q.push (std::make_pair (0, 0)), vis[0][0] = 0;
while (!q.empty ()) {
int u = q.front ().first, st = q.front ().second; q.pop ();
// printf ("%lld %lld %lld %lld %lld %lld\n", u, st, vis[u][st], la[u][st], ch[u][st], lst[u][st]);
if (st == ST) return u;
_for (i, 0, 25) {
int v = nxt[u][i];
int sta = st | end[v];
if (vis[u][st] + 1 >= vis[v][sta]) continue;
vis[v][sta] = vis[u][st] + 1;
la[v][sta] = u, ch[v][sta] = i, lst[v][sta] = st;
q.push (std::make_pair (v, sta));
// printf ("%lld %lld %lld\n", v, sta, i);
}
}
return 0;
}
inline void Print (int p, int sta) {
if (!p) return;
Print (la[p][sta], lst[p][sta]);
putchar (ch[p][sta] + 'A');
return;
}
};
}
namespace SOLVE {
int n, m, t, ans, c[15]; char s[15][60];
ACAUTOMATON::ACAutomaton ac;
inline int rnt () {
int x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline bool Compare (char *s1, char *s2) {
int l1 = strlen (s1 + 1), l2 = strlen (s2 + 1);
_for (i, 1, l2) {
int flag = 0;
_for (j, 1, l1) {
if (s2[i + j - 1] != s1[j]){
flag = 1;
break;
}
}
if (!flag) return 1;
}
return 0;
}
inline void In () {
n = rnt ();
_for (i, 1, n) scanf ("%s", s[i] + 1);
_for (i, 1, n) {
_for (j, 1, n) {
if (i == j) continue;
if (strlen (s[i] + 1) >= strlen (s[j] + 1)) continue;
c[i] = Compare (s[i], s[j]);
}
}
_for (i, 1, n) {
if (c[i]) continue;
t |= 1 << (i - 1), ac.Insert (s[i], i);
}
return;
}
inline void Solve () {
ac.Build ();
ans = ac.BFS (n, t);
return;
}
inline void Out () {
ac.Print (ans, t);
puts ("");
return;
}
}
int main () {
#ifndef ONLINE_JUDGE
freopen ("date.in", "r", stdin);
#endif
SOLVE::In ();
SOLVE::Solve ();
SOLVE::Out ();
return 0;
} /*
*/
```
by K8He @ 2023-04-23 19:01:52
[不 MLE 了，现在 WA 了](https://www.luogu.com.cn/record/108782167)
by K8He @ 2023-04-23 19:21:58
@[Keven_He](/user/306045)
```
end[nxt[u][i]] |= end[fail[nxt[u][i]]]
```
by Delov @ 2023-04-23 20:16:50
@[Keven_He](/user/306045) 状态是继承失配树上的
by Delov @ 2023-04-23 20:18:04
@[Delov](/user/277792) 谢谢您！已经过了！
事实上去重的部分也有问题，应该是：`c[i] |= Compare (s[i], s[j]);`。
by K8He @ 2023-04-23 20:28:59