HDOJ 4763 Theme Section：Extended KMP 求最大主題段長度

題目大意

• 給定字串 S（長度 ≤ 10⁶），尋找最大長度 L，使 S 可表示為 E A E B E，其中 E 為長度 L 的前綴/中段/後綴，A、B 任意（可為空）。
• 即：S 以 E 開頭，中間某處出現 E，結尾以 E 結尾，三段 E 不重疊。

核心觀察

• 設 E 長度為 L，則 S[0..L-1] = E，S[n-L..n-1] = E。
• 中間必須存在一個位置 i (L ≤ i ≤ n-2L) 使 S[i..i+L-1] = E。
• 等價：L 滿足 L ≤ n/3 且 E 為前綴、後綴，且在 [L, n-2L] 區間內出現。

Extended KMP (ExKMP) 算法

ExKMP 在 O(n) 計算：

• next[i]：模式串 P[i..] 與 P[0..] 的最長公共前綴 (LCP)。
• ex[i]：文本串 T[i..] 與 P[0..] 的 LCP。

本題取 P = S、T = S，故 ex[i] = next[i]。

演算法流程

1. 計算 next[] 陣列。
2. 枚舉 L 從大到小（或枚舉中間位置 i），檢查：
   • next[i] ≥ L 確保中間匹配。
   • next[n-L] ≥ L 確保後綴匹配（實際上 next[n-L] 即為後綴與前綴 LCP）。
3. 滿足條件的最大 L 即為答案。

關鍵代碼片段

void pre_exkmp(char *P) {
    int m = strlen(P);
    next[0] = m;
    int j = 0, k = 1;
    while (j+1 < m && P[j] == P[j+1]) ++j;
    next[1] = j;
    for (int i = 2; i < m; ++i) {
        int p = next[k] + k - 1;
        int L = next[i - k];
        if (i + L < p + 1) next[i] = L;
        else {
            j = max(0, p - i + 1);
            while (i + j < m && P[i+j] == P[j]) ++j;
            next[i] = j; k = i;
        }
    }
}

int solve(char *S) {
    int n = strlen(S);
    pre_exkmp(S);
    int ans = 0;
    for (int i = 1; i + ans < n; ++i) {
        int Len = min(next[i], i);
        while (n - Len < i + Len && Len > ans) --Len;
        if (Len <= ans) continue;
        for (int j = n - Len; j < n - ans; ++j) {
            if (next[j] >= n - j) { ans = max(ans, n - j); break; }
        }
    }
    return ans;
}

複雜度分析

• 時間：O(n) ExKMP + O(n) 枚舉 = O(n)。
• 空間：O(n) 存 next[]。
• 單測資 n ≤ 10⁶，多測資總長度通常受限，C/C++ 輕鬆通過。

樣例驗證

Input:
5
xy
abc
aaa
aaaaba
aaxoaaaaa

Output:
0
0
1
1
2

• aaa：E="a"，A=""，B="" → a a a，L=1。
• aaxoaaaaa：E="aa"，A="xo"，B="a" → aa xo aa a 尾部補齊，L=2。