UVA 11475 Extend to Palindrome（KMP 求最短回文擴展）

UVA 11475 Extend to Palindrome - KMP 字符串匹配

給定字符串，在末尾添加最少字符使其成為回文串。輸出結果串。

KMP 解法核心思想

設原串為 S，逆序串為 R。求 R 的最長前綴與 S 的最長後綴匹配。即：在 R 中找到與 S 尾部最長匹配的前綴。

構造模式串 R，文本串 S，跑 KMP 匹配。匹配到 S 末尾時，R 中已匹配長度 = 最大重疊長度。需補充 R 剩餘部分。

完整代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXL = 100005;

struct KMP {
    int nxt[MAXL];
    void buildNext(const char* s) {
        int n = strlen(s);
        nxt[1] = 0;
        for (int i = 2, j = 0; i <= n; i++) {
            while (j && s[j] != s[i-1]) j = nxt[j];
            if (s[j] == s[i-1]) j++;
            nxt[i] = j;
        }
    }
    void find(const char* text, const char* pat) {
        int n = strlen(text);
        buildNext(pat);
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j && text[i] != pat[j]) j = nxt[j];
            if (text[i] == pat[j]) j++;
        }
        // j 為最大匹配長度
        printf("%s%s\n", text, pat + j);
    }
} kmp;

char s[MAXL], rev[MAXL];

int main() {
    while (~scanf("%s", s)) {
        strcpy(rev, s);
        reverse(rev, rev + strlen(rev));
        kmp.find(s, rev);
    }
    return 0;
}

算法解釋

• S = "abcb"，R = "bcba"
• KMP 匹配 S vs R：
• 匹配到 S 末尾時，j = 3 ("bcb")
• 需補充 R[3..] = "a"
• 結果："abcb" + "a" = "abcba"

複雜度分析

• 構建 next：O(n)
• KMP 匹配：O(n)
• 總時間：O(n)，n ≤ 100,000

避坑指南

• 多測試用例直到 EOF
• 字符串長度可能大，數組開夠大
• KMP 下標小心：模式串 1-based，文本串 0-based