HDU 4300 Clairewd's Message：KMP 邊界匹配還原最短完整文本

題目大意

給定 26 字母加密表 S（S[i] 是明文 'a'+i 對應的密文字符）和截獲文本 T（密文+明文拼接，密文在前，明文在後，可能不全）。求最短可能的完整文本（密文全+明文全）。

核心觀察

• 密文長度 ≥ 明文長度（因密文在前）。
• 設 len = |T|，則前 ⌈len/2⌉ 必屬於密文部分。
• 將前半部分按逆表解密得到候選明文，再與後半部分匹配，找到最長公共前綴/後綴邊界。

算法流程

1. 構建逆映射 dec[cipher] = plain。
2. 取 k = (len-1)/2，前 k+1 字符解密得 P。
3. 在 T 中從位置 k 開始，找最長後綴與 P 的前綴匹配（KMP 或雙指針）。
4. 匹配位置即為明文起始點，輸出 T + P[匹配長度:]。

代碼片段（關鍵 KMP 部分）

// 逆表
char dec[256];
for (int i=0;i<26;++i) dec[S[i]] = 'a'+i;
// 解密前半
string P;
for (int i=0;i<=k;++i) P += dec[T[i]];
// KMP 在 T[k..] 中匹配 P
// ... 省略標準 KMP ...
// 輸出 T + P.substr(match_len)

複雜度

• 時間：O(n)，KMP 線性。
• 空間：O(n)。

關鍵點

1. 密文一定比明文長或等長 → 前半必含完整密文。
2. KMP 找「明文部分在解密密文中的最長前綴匹配」等價於找分界點。
3. 樣例 1：S=abc..., T=abcdab → 解密前半 abcdab → 匹配得完整 abcdabcd。