Codeforces 127D Password：KMP 前綴函數求最長合法子串

Codeforces 127D Password 解題報告：前綴=後綴且中間出現

給定字符串 s（長度 ≤ 10^6），找最長子串 t 滿足：

1. t 是 s 的前綴；
2. t 是 s 的後綴；
3. t 在 s 的中間（非首尾）至少出現一次。

不存在則輸出 Just a legend。

KMP Next 數組核心性質

next[i] = 模式串前 i 字符的最長真前綴 = 真後綴長度。
遞推：next[len] 是整個字符串最長邊長（既是前綴又是後綴）。
next[next[len]] 是次長邊長，以此類推，構成邊長鏈。

解題邏輯

1. 計算 next[] 數組。
2. 統計所有 next[i] (1 ≤ i < len) 出現的長度，標記 vis[length] = true，表示該長度的前綴在中間出現過。
3. 從最長邊長 L = next[len] 開始，沿鏈 L = next[L] 遞減檢查：
   若 vis[L] 為真，說明長度 L 的前綴滿足「前綴=後綴且中間出現」，即為答案。
   若鏈走到 0 仍無，則無解。

為什麼跳 next[L]？

若當前最長邊長 L 不滿足「中間出現」，則任何更長的邊長也不存在（因 L 已是最長）。下一個候選必須是 L 的邊，即 next[L]。這保證了檢查順序為「從長到短」，首個滿足即最長答案。

關鍵代碼

void getFail(char* s) {
    int n = strlen(s);
    next[0] = -1;
    for(int i=0, j=-1; i 0) {
            if(vis[L]) { s[L] = '\0'; puts(s); break; }
            L = next[L];
        }
        if(L == 0) puts("Just a legend");
    }
    return 0;
}

複雜度

• 時間：O(n)（KMP 構建 + 線性掃描）。
• 空間：O(n)（next、vis 數組）。

易錯點

• vis 數組大小需 ≥ n+1。
• next[0] = -1 寫法下，next[i] 存儲長度，i 從 1 開始對應前 i 字符。
• 輸出時直接截斷原字符串 s[L]='\0' 輸出 s，避免拷貝。