HDU 4300 Clairewd's Message：KMP 解密還原完整字符串

題目大意

給定一個替換表（第 i 個字母用哪個字母表示），以及一個字符串，前半部為密文，後半部為明文（密文完整，明文可能不全）。利用替換表將密文轉為明文，再用 KMP 求出明文的最長前綴與密文轉換後字符串的最長後綴匹配，從而還原完整字符串。

解題步驟

1. 讀入替換表 a1（26 字母映射）和目標串 a2。
2. a2 前半為密文，後半為明文。設 len = strlen(a2)，明文部分為 a3 = a2 + (len+1)/2。
3. 將 a2 整體按替換表轉換為明文字符（即密文按表解密）。
4. 對轉換後的串（即全明文）構建 KMP next 數組。
5. 用 KMP 匹配 a3（明文後綴）在轉換後串中的位置，找到最長匹配前綴長度 flag。
6. 輸出：原密文 + 轉換後明文中未被 a3 覆蓋的部分（即 a2[flag ... len-flag-1]）。

關鍵代碼

邏輯圖解
原始 a2: [ 密文 (完整) ][ 明文 (部分) ]
           |←--- len ---→|
轉換後 a2: [ 明文全文 (由密文解密得) ]
                    ↑
              KMP 匹配 a3 (明文後綴)
              找到最長前綴匹配長度 flag
最終輸出: 密文 + 轉換後明文[flag ... len-flag-1]


關鍵點

替換表 a1 索引 0~25 對應 'a'~'z'，a1[j] 是密文中代表明文 'a'+j 的字符。解密時查找 a2[i] == a1[j] 則明文為 'a'+j。
KMP 匹配方向：在「轉換後的全明文」中尋找「原明文後綴」的最長前綴匹配。
輸出拼接：先輸出原密文，再輸出轉換後明文中未被原明文覆蓋的中間部分。


複雜度
字符串長度 ≤ 1e5，KMP O(n)，總時間 O(T·n)，空間 O(n)，完全滿足限制。