最短母串

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2655 字
AC 自动机上状态加掩码 BFS 求最短母串
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1483
// 题意：给 n 个大写字符串，求一个最短的串 T 使这 n 个串都是 T 的子串；长度相同字典序最小。
// 思路：建 AC 自动机并预处理每个状态「到达后已包含哪些串」的位掩码，然后在 (自动机状态, 掩码) 上做 BFS，第一次到达全 1 掩码即为最短；每次按 A..Z 顺序扩展，BFS 队首保证同长时字典序最小。
// 复杂度：O(状态数 × 2^n × 26) 时间 / O(状态数 × 2^n) 空间
// 易错点：状态掩码要沿 fail 链合并（out[u] |= out[fail[u]]），否则某个短串作为长串的后缀出现时不会被记录。
// 易错点：字典序最小靠「按 A..Z 顺序入队 + 每个状态只访问一次」，不能只按长度贪心拼接。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[26];
    int fail;
    int out;
    Node(){
        memset(ch, 0, sizeof(ch));
        fail = 0;
        out = 0;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin >> n)) return 0;
    vector<Node> tr;
    tr.reserve(n * 50 + 1);
    tr.push_back(Node());
    for(int i = 0; i < n; i++){
        string w;
        cin >> w;
        int u = 0;
        for(int j = 0; j < (int)w.size(); j++){
            int c = w[j] - 'A';
            if(!tr[u].ch[c]){
                tr[u].ch[c] = (int)tr.size();
                tr.push_back(Node());
            }
            u = tr[u].ch[c];
        }
        tr[u].out |= (1 << i);
    }
    queue<int> q;
    for(int c = 0; c < 26; c++){
        if(tr[0].ch[c]) q.push(tr[0].ch[c]);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        tr[u].out |= tr[tr[u].fail].out;
        for(int c = 0; c < 26; c++){
            int v = tr[u].ch[c];
            if(v){
                tr[v].fail = tr[tr[u].fail].ch[c];
                q.push(v);
            }else{
                tr[u].ch[c] = tr[tr[u].fail].ch[c];
            }
        }
    }
    int sz = (int)tr.size();
    int full = (1 << n) - 1;
    int totalState = sz * (full + 1);
    vector<int> preS(totalState, -1);
    vector<int> preC(totalState, -1);
    vector<char> vis(totalState, 0);
    queue<int> bfs;
    int start = 0;
    vis[start] = 1;
    bfs.push(start);
    int goal = -1;
    while(!bfs.empty()){
        int cur = bfs.front();
        bfs.pop();
        int u = cur / (full + 1);
        int mask = cur % (full + 1);
        if(mask == full){
            goal = cur;
            break;
        }
        for(int c = 0; c < 26; c++){
            int v = tr[u].ch[c];
            int nm = mask | tr[v].out;
            int nid = v * (full + 1) + nm;
            if(vis[nid]) continue;
            vis[nid] = 1;
            preS[nid] = cur;
            preC[nid] = c;
            bfs.push(nid);
        }
    }
    string ans;
    int cur = goal;
    while(cur != start){
        ans.push_back((char)('A' + preC[cur]));
        cur = preS[cur];
    }
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
    return 0;
}
最短母串

正文

一本通·提高篇的其它内容
