UVA 11019 Matrix Matcher 題解：AC 自動機多模式匹配二維矩陣 O(N×M + X×Y) 解法

題目大意

給定 N×M 文字矩陣 T (N,M ≤ 1000) 和 X×Y 模式矩陣 P (X,Y ≤ 100)。求 P 在 T 中出現的次數 (允許重疊)。多測資 t ≤ 15，輸入約 7MB，需快速 I/O。

核心洞察：逐行 AC 自動機 + 列計數器

1. 將模式矩陣 P 的每一行視為一個模式串，建立 AC 自動機。
2. 對文本矩陣 T 的每一行跑 AC 自動機，得到該行每個位置匹配的模式行號。
3. 若在第 r 行、第 c 列匹配到模式第 k 行，說明 T[r][c..c+Y-1] == P[k]。
4. 維護計數器 cnt[r - k + 1][c] (模式左上角位置)。若某位置計數達到 X，說明 X 行連續匹配，完整出現一次。

AC 自動機關鍵結構

struct AhoCorasick {
    static const int MAXN = 1000000;  // 總模式長度 ≤ 100×100 = 10000
    static const int SIGMA = 26;
    int ch[MAXN][SIGMA]{};
    int fail[MAXN]{};
    vector out[MAXN];  // 該節點結尾的模式行號 (可能多行相同)
    int sz = 1;
    
    void insert(const string& s, int id) {
        int u = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (!this->ch[u][c]) this->ch[u][c] = sz++;
            u = this->ch[u][c];
        }
        out[u].push_back(id);
    }
    
    void build() {
        queue q;
        for (int c = 0; c < SIGMA; c++) {
            if (ch[0][c]) q.push(ch[0][c]);
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int c = 0; c < SIGMA; c++) {
                int v = ch[u][c];
                if (!v) {
                    ch[u][c] = ch[fail[u]][c];
                } else {
                    fail[v] = ch[fail[u]][c];
                    // 合併輸出：失敗鏈上的模式也屬於當前節點輸出
                    for (int id : out[fail[v]]) out[v].push_back(id);
                    q.push(v);
                }
            }
        }
    }
    
    // 在文本行中查找，回傳每個位置匹配的模式行號列表
    void search(const string& text, int row, vector>& matches) {
        int u = 0;
        for (int i = 0; i < text.size(); i++) {
            int c = text[i] - 'a';
            u = ch[u][c];
            for (int id : out[u]) {
                matches[row][i].push_back(id);  // row行第i列匹配到模式第id行
            }
        }
    }
};

完整解題流程

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int N, M; cin >> N >> M;
        vector Tmat(N);
        for (int i = 0; i < N; i++) cin >> Tmat[i];
        
        int X, Y; cin >> X >> Y;
        vector Pmat(X);
        for (int i = 0; i < X; i++) cin >> Pmat[i];
        
        AhoCorasick ac;
        for (int i = 0; i < X; i++) ac.insert(Pmat[i], i);  // id = 0..X-1
        ac.build();
        
        // matches[r][c] = 匹配到的模式行號列表
        vector>> matches(N, vector>(M));
        for (int r = 0; r < N; r++) ac.search(Tmat[r], r, matches);
        
        // 計數器 cnt[r][c] = 以(r,c)為左上角連續匹配的行數
        vector> cnt(N, vector(M, 0));
        int ans = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                for (int pid : matches[r][c]) {
                    int start_r = r - pid;  // 模式左上角行
                    if (start_r >= 0) {
                        if (++cnt[start_r][c] == X) ans++;
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度分析

• 建立 AC：O(X×Y × Σ) ≈ 260,000
• 搜尋文本：O(N×M) 每字元 O(1) 狀態轉移
• 計數統計：O(總匹配數) ≤ O(N×M×X) 但實際極小
• 總時間：O(N×M + X×Y) 線性，極快通過 7MB 輸入。
• 空間：O(X×Y×Σ) 自動機 + O(N×M) 計數器 ≈ 40MB 內。

關鍵細節與避坑

即時計數優化版 (省記憶體)

// search 時直接更新 cnt，無需儲存 matches
void search_and_count(const string& text, int row, vector>& cnt, int X) {
    int u = 0;
    for (int c = 0; c < text.size(); c++) {
        u = ch[u][text[c]-'a'];
        for (int pid : out[u]) {
            int sr = row - pid;
            if (sr >= 0 && ++cnt[sr][c] == X) ans++;
        }
    }
}

經典模式：二維模式匹配 = 一維 AC 自動機 + 幾何計數器。將二維問題分解為「行內多模式匹配」+「跨行幾何對齊」，是處理矩陣/圖像模式識別的通用套路。AC 自動機保證行內匹配線性時間，計數器解決幾何拓撲對齊。