BZOJ 2555 SubString：後綴自動機 (SAM) 線上查詢出現次數

題目大意

維護一個動態字串，支援兩種操作：
1. Append：在字串尾端新增一子串。
2. Query：詢問一模式串在當前字串中出現次數。
採用線上編碼：每次操作前將輸入串經過 mask 置換解碼。

核心資料結構：後綴自動機 (SAM)

SAM 是一種有限自動機，能以 O(n) 時空建構，表示字串所有子串。每個狀態對應一個 endpos 等價類，關鍵屬性：

• len：該等價類最長子串長度。
• link (父節點)：指向最長真後綴對應的狀態。
• trans[c]：轉移邊。
• size (或 cnt)：該狀態代表的子串在原字串中出現次數 (即 endpos 集合大小)。

關鍵操作：擴展與分裂

擴展字元 c

void Add(int c) {
    State* np = new State(last->len + 1);
    State* p = last;
    while (p && !p->trans[c]) p->trans[c] = np, p = p->link;
    if (!p) np->link = root;
    else {
        State* q = p->trans[c];
        if (q->len == p->len + 1) np->link = q;
        else {
            State* nq = new State(p->len + 1);
            nq->trans = q->trans; // 複製轉移
            nq->link = q->link;
            nq->size = q->size;   // **關鍵：分裂節點需複製 size**
            q->link = np->link = nq;
            while (p && p->trans[c] == q) p->trans[c] = nq, p = p->link;
        }
    }
    last = np;
    // 更新 size：沿 suffix link 往上累加
    for (State* t = np; t != root; t = t->link) t->size++;
}

查詢模式串出現次數

int Ask(string s) {
    State* now = root;
    for (char ch : s) {
        int c = ch - 'A';
        if (!now->trans[c]) return 0; // 不存在
        now = now->trans[c];
    }
    return now->size;
}

線上解碼機制

每次讀入操作串 s 後，執行：

void DecodeWithMask(int mask) {
    int len = s.length();
    for (int i = 0; i < len; ++i) {
        mask = (mask * 131 + i) % len;
        swap(s[i], s[mask]);
    }
}

查詢答案 last_ans 會更新 mask ^= last_ans，確保線上性。

複雜度分析

• 建構 SAM：O(N) (N 為總字串長度)
• 單次查詢：O(|P|) (P 為模式串長度)
• 總記憶體：O(N) 狀態數 ≤ 2N

注意事項

1. 分裂節點 nq **必須複製 q->size**，否則出現次數統計錯誤。
2. 查詢中途轉移不存在直接回傳 0。
3. 陣列大小開 2 * 最大總長度 (題目通常 4e6)。