HDU 4763 Theme Section：KMP 失配函數變形求前中後三現子串最大長度

題目轉化

給定字符串 s，找最長子串 t，使其在 s 的前綴、中間、後綴各出現一次（可重疊）。即：t 是 s 的前綴、後綴，且在中間至少出現一次。

KMP 失配函數性質

f[i] = 模式串前 i 字符的最長真前綴=後綴長度。遞推：f[i+1] 由 f[i] 跳轉得到。

關鍵觀察

對整個串 s 計算 f[len]。若 f[len] > 0，則長度為 f[len] 的前綴 = 後綴。再檢查該前綴是否在中間（位置 1 到 len-2）出現。

遞歸檢查

1. 令 j = f[len]
2. 若 len >= 3*j 且中間存在長度 j 的前綴 → 答案 j
3. 否則 j = f[j] 繼續檢查更短的前綴=後綴

中間出現判定

在 s[j ... len-j-1] 中尋找模式 s[0 ... j-1]，可用 KMP 匹配或 strstr。

代碼核心

void getFail(char* p, int m) {
    f[0]=f[1]=0;
    for (int i=1;i= 3*j && strstr(s+j, s) - s < len - j) 
                { ans = j; break; }
            j = f[j];
        }
        printf("%d\n", ans);
    }
}

複雜度

KMP 預處理 O(n)，每次檢查 O(n)，最多 O(log n) 次遞歸，總體 O(n log n) 或 O(n) 視實現而定。