UVA 10679 I love Strings!!!：AC 自動機多模式匹配

問題描述

給定文本串 S (|S| < 100,001) 和 q (<100) 個模式串 T (|T| ≤ 1000)，判斷每個 T 是否為 S 的子串。大小寫敏感。

AC 自動機原理

• 構建模式串 Trie 樹
• 構建失敗指針 (fail)：類似 KMP 的 next 數組，指向最長真後綴對應的節點
• 輸出鏈 (last/out)：鏈接所有以該節點結尾的模式串
• 文本掃描：O(|S|) 時間內同時匹配所有模式

關鍵數據結構

struct ACauto {
    int ch[maxn][maxsize]; // 轉移
    int val[maxn];         // 節點對應模式串編號 (0 表示無)
    int fail[maxn];        // 失敗指針
    int last[maxn];        // 輸出鏈
    int sz;                // 節點總數
};

核心操作

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int maxsize = 52; // A-Z, a-z
const int maxn = 1000007;

int idx(char c) { return islower(c) ? c-'a'+26 : c-'A'; }

struct ACauto { /* 如上定義 */ } ac;

char T[maxn], P[233];
bool found[107];
int id[107];

int main() {
    int kase; scanf("%d", &kase);
    while (kase--) {
        ac.clear();
        scanf("%s", T);
        int q; scanf("%d", &q);
        for (int i = 1; i <= q; ++i) {
            scanf("%s", P);
            id[i] = ac.insert(P, i);
            found[i] = false;
        }
        ac.find(T);
        for (int i = 1; i <= q; ++i)
            putchar(found[id[i]] ? 'y' : 'n'), putchar('\n');
    }
    return 0;
}

複雜度

• 構建：O(總模式長度 × 字符集)
• 匹配：O(|S|)
• 空間：O(總模式長度 × 字符集)
• 完美滿足題目約束 (|S|≤1e5, q≤100, |T|≤1000)