HDU 4763 Theme Section：KMP 算法求字符串最大主題段長度

問題描述

給定字符串 S（長度 ≤ 10^6），找到最長子串 E，使得 S 可表示為 `E A E B E` 形式（A、B 為任意子串，可為空）。即 E 同時作為前綴、中間某處、後綴出現，三次出現不重疊。輸出最大可能的 |E|。

核心觀察

• E 必須是 S 的前綴，也是 S 的後綴
• E 的長度 ≤ |S|/3（三次不重疊）
• 需在 S[|E| ... |S|-|E|-1] 中找到 E 的出現

算法策略：枚舉長度 + KMP 驗證

1. 枚舉候選長度

從最大可能長度 `n/3` 遞減到 1，檢查前綴 `S[0..len-1]` 是否同時滿足：

• 是後綴：`S[n-len..n-1] == S[0..len-1]`
• 在中間區間出現：用 KMP 在 `S[len..n-len-1]` 中搜索模式串 `S[0..len-1]`

2. KMP 預處理與匹配

void getnext(int m) {
    int i=0, j=-1; next[0]=-1;
    while (i < m) {
        if (j==-1 || s[i]==s[j]) {
            i++; j++;
            if (s[i]!=s[j]) next[i]=j;
            else next[i]=next[j];
        } else j=next[j];
    }
}

int kmp(int m) {  // 在全局 str 中搜索模式串 s[0..m-1]
    int i=0, j=0;
    while (i < n) {
        if (j==-1 || str[i]==s[j]) { i++; j++; }
        else j=next[j];
        if (j==m) return 1;
    }
    return 0;
}

3. 主流程

void work(char* s, int m) {
    while (m) {
        int i=0;
        for (int j=n-m; j

優化與複雜度

枚舉長度最多 n/3 次
每次 KMP O(n)，總體 O(n²/3) 理論上可能超時
實際上：後綴檢查極快，KMP 只在極少數候選長度觸發，實測通過
更優解法：Z-algorithm 或後綴自動機可達 O(n)，但 KMP 實現簡單且常數小


樣例驗證
Input:  aaxoaaaaa  (n=9)
len=3: "aax" 後綴 "aaa" 不匹配
len=2: "aa"  後綴 "aa" 匹配，中間 "xoaaa" 含 "aa" → 答案 2


總結
本題是 KMP 算法的經典應用變體，核心技巧在於從大到小枚舉候選長度，利用前綴/後綴性質快速過濾，僅對少量候選執行 KMP 搜索。展示了「暴力枚舉 + 高效驗證」在字符串問題中的實用性。