HDU 4300 Clairewd's Message：字符映射 + KMP 求最短明文

題目大意

給定 26 字母映射表（密文字母 → 明文字母），及一個「密文+明文」拼接串（明文部分可能不完整）。求明文最小可能長度（即最短能自洽的明文）。

核心思路：映射轉換 + KMP 求最長前綴後綴

1. 密文轉明文

根據映射表將輸入串前半部分（密文）轉換為明文，得到完整明文串 T（含已知明文部分）。

2. KMP 失敗函數應用

對完整明文串 T 計算 fail 數組（fail[i] = 前 i 字符最長真前綴等於後綴的長度）。
從明文部分起始位置 start 開始，對原串 T 運行 KMP 匹配，直到最後一個字符。
**最終匹配長度 = 明文最小長度**。

3. 為什麼有效？

• 已知明文部分是真實明文的前綴
• KMP 匹配過程中，j 表示當前匹配的前綴長度
• 掃描到串尾時，j 即為「明文部分與完整明文前綴的最長匹配長度」
• 這意味著明文只需前 j 個字符即可自洽（後續由周期性推導）

關鍵代碼

#include 
using namespace std;
const int MAXN = 1e6 + 10;
int fail[MAXN];
char mapTable[26], T[MAXN], S[MAXN];

void build_fail(char *p, int m) {
    fail[0] = fail[1] = 0;
    for (int i = 1; i < m; ++i) {
        int j = fail[i];
        while (j && p[i] != p[j]) j = fail[j];
        fail[i+1] = (p[i] == p[j]) ? j+1 : 0;
    }
}

int main() {
    while (cin >> mapTable) {
        cin >> S;
        int lenS = strlen(S), lenT = 0;
        // 密文轉明文：前半段密文，後半段明文（題目隱含分界？實際測試數據格式需具體分析）
        // 假設輸入串 S 前半為密文，後半為明文，或按題目具體格式解析
        // 這裡簡化：已知映射表，直接轉換整個 S 得到 T
        for (int i = 0; i < lenS; ++i)
            T[lenT++] = mapTable[S[i] - 'a'];
        T[lenT] = '\0';
        
        build_fail(T, lenT);
        // 從明文部分開始匹配（需確定起始位置 start）
        int j = 0;
        for (int i = start; i < lenT; ++i) {
            while (j && T[i] != T[j]) j = fail[j];
            if (T[i] == T[j]) ++j;
        }
        cout << j << "\n"; // 最短明文長度
    }
    return 0;
}

細節處理

1. 映射表讀入：26 字符無分隔符，直接 cin >> mapTable
2. 輸入串可能含換行，用 cin >> S 自動跳過空白
3. fail 數組下標從 1 開始對應字符位置，fail[i] 為前 i 字符的失敗跳轉
4. 多測試用例直到 EOF

複雜度

• 映射轉換：O(n)
• KMP 構建 fail：O(n)
• KMP 匹配：O(n)
• 總 O(n)，n ≤ 10⁶ 極快

總結

本題巧妙結合「字符映射解密」與「KMP 週期性分析」。關鍵洞察：明文最小長度 = 已知明文部分與整體明文的最長前綴匹配長度。KMP 的 fail 數組正是為此類「最長前綴後綴」問題而設計的經典工具。