玄武密码

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2275 字
AC 自动机跑母串标记状态查最长前缀
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1480
// 题意：给一个长度为 N 的母串（只含 E/S/W/N）和 M 段文字，求每段文字的前缀能在母串中匹配到的最大长度。
// 思路：把所有文字段插入 Trie 并建成完全 AC 自动机（把 fail 转移回填到 ch 里），母串在自动机上走一遍并标记到过的状态；之后用文字段走自动机，最深的被标记状态的长度即为答案。
// 复杂度：O(N + 所有文字段总长) 时间 / O(所有文字段总长 × 4) 空间
// 易错点：文字段的前缀本身一定是 Trie 结点，所以把 ch 回填成完全转移后，用文字段走自动机到达的状态仍等于该前缀的 Trie 结点，不需要另存一份原图。
// 易错点：母串可能长达 10^7，必须用 scanf/快读或关同步的 cin，且 Trie 结点数按总长度开够，不能开固定小数组。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[4];
    Node(){
        ch[0] = ch[1] = ch[2] = ch[3] = 0;
    }
};
int idOf(char c){
    if(c == 'E') return 0;
    if(c == 'S') return 1;
    if(c == 'W') return 2;
    return 3;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if(!(cin >> N >> M)) return 0;
    string s;
    cin >> s;
    vector<string> pat(M);
    int total = 0;
    for(int i = 0; i < M; i++){
        cin >> pat[i];
        total += (int)pat[i].size();
    }
    vector<Node> tr;
    tr.reserve(total + 1);
    tr.push_back(Node());
    for(int i = 0; i < M; i++){
        int u = 0;
        for(int j = 0; j < (int)pat[i].size(); j++){
            int c = idOf(pat[i][j]);
            if(!tr[u].ch[c]){
                tr[u].ch[c] = (int)tr.size();
                tr.push_back(Node());
            }
            u = tr[u].ch[c];
        }
    }
    vector<int> fail(tr.size(), 0);
    queue<int> q;
    for(int c = 0; c < 4; c++){
        if(tr[0].ch[c]) q.push(tr[0].ch[c]);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int c = 0; c < 4; c++){
            int v = tr[u].ch[c];
            if(v){
                fail[v] = tr[fail[u]].ch[c];
                q.push(v);
            }else{
                tr[u].ch[c] = tr[fail[u]].ch[c];
            }
        }
    }
    vector<int>().swap(fail);
    int sz = (int)tr.size();
    vector<char> vis(sz, 0);
    int u = 0;
    vis[0] = 1;
    for(int i = 0; i < (int)s.size(); i++){
        u = tr[u].ch[idOf(s[i])];
        vis[u] = 1;
    }
    for(int i = 0; i < M; i++){
        int p = 0;
        int best = 0;
        for(int j = 0; j < (int)pat[i].size(); j++){
            p = tr[p].ch[idOf(pat[i][j])];
            if(vis[p]) best = j + 1;
        }
        cout << best << "\n";
    }
    return 0;
}
玄武密码

正文

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