嘘~ 正在从服务器偷取页面 . . .

洛谷P2322 [HNOI2006] 最短母串问题题解

发布日期: 2024-06-12

更新日期: 2024-06-12

文章字数: 738

洛谷P2322 [HNOI2006] 最短母串问题题解

题目链接：P2322 [HNOI2006] 最短母串问题

题意：

给定 $n$ 个字符串 $(S_1,S_2,…,S_n)$ ，

要求找到一个最短的字符串 $T$，使得这 $n$ 个字符串 $(S_1,S_2,…,S_n)$ 都是 $T$ 的子串。

输入格式：

输入文件第一行是一个整数 $n$，表示给定的字符串个数。

接下来 $n$ 行，每行有一个全由大写字母组成的字符串。

输出格式：

输出文件只有一行，为找到的最短的字符串 $T$。

在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。

数据范围：

对于 $100\%$ 的数据，$n \leq 12$，每个字符串的长度不超过 $50$。

由于本题要求输出字典序最小的方案，所以这题状压dp会比较麻烦。

注意到超级小的数据范围，考虑暴力出奇迹，即 bfs 所有可能的情况。

检验的话，考虑将题目给的串建一个 AC 自动机，然后预处理出每个节点包含了那些串。

由于一般的写法都是建字典图，所以只需要在队列里记录当前节点和状态即可。

时间复杂度 $\mathcal{O}(26\cdot2^n\sum |s_i|)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(666))
#define M (N * (1 << 12))

char s[N], vis[N][6666];
int n, tot, fail[N], ed[N], trie[N][26], stk[N], fa[M], ans[M];
void build()
{
    queue<int> q;
    for(int i = 0; i < 26; i++) if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = 0; i < 26; i++)
            if(trie[u][i])
            {
                fail[trie[u][i]] = trie[fail[u]][i];
                ed[trie[u][i]] |= ed[trie[fail[u]][i]]; q.push(trie[u][i]);
            }else { trie[u][i] = trie[fail[u]][i]; }
    }
}
queue<pii> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> (s + 1); int u = 0;
        for(int j = 1, c = 0; s[j]; u = trie[u][c], j++)
        {
            c = s[j] - 'A';
            if(!trie[u][c]) trie[u][c] = ++tot;
        }
        ed[u] |= 1 << (i - 1);
    }
    build(); q.push({0, 0}); vis[0][0] = true;
    for(int tim = 0, cnt = 0; !q.empty(); ++tim)
    {
        auto [u, st] = q.front(); q.pop();
        if(st == (1 << n) - 1)
        {
            int top = 0, p = tim;
            while(p) { stk[++top] = ans[p]; p = fa[p]; }
            while(top) cout << (char)stk[top--];
            return cout << '\n', 0;
        }
        for(int i = 0; i < 26; i++)
        {
            const int v = trie[u][i], t = st | ed[v]; // 暴力出奇迹
            if(!vis[v][t])
            {
                vis[v][t] = true; q.push({v, t});
                fa[++cnt] = tim; ans[cnt] = i + 'A';
            }
        }
    }
    return 0;
}