力扣214题：从暴力算法到KMP算法解决最短回文串

一、问题理解

回文串是指正读反读都相同的字符串，如"abba"、"abcba"。题目要求我们在给定字符串前面添加最少的字符，使其成为回文串。

二、解决思路

1. ‌暴力解法‌：最直观的方法是检查字符串的每个前缀是否是回文，找到最长的回文前缀，然后将剩余部分反转后添加到前面。这种方法时间复杂度为O(n²)。

2. ‌优化解法‌：使用KMP算法中的部分匹配表(PMT)思想，可以线性时间内解决问题。

三、KMP算法思想的应用

KMP算法原本用于字符串匹配，其核心是部分匹配表(PMT)，记录了模式串中"前缀"和"后缀"的最长公共元素长度。

在本题中，我们可以：

1. 将原字符串s和其反转字符串rev_s组合，中间用特殊字符分隔

2. 为这个组合字符串构建PMT表

3. PMT表的最后一个值就是s中最长回文前缀的长度

4. 将rev_s去掉这个最长回文前缀的部分添加到s前面，就得到最短回文串

四、完整代码

class Solution {
public:
    string shortestPalindrome(string s) {
        // 使用KMP算法中的部分匹配表(Partial Match Table)思想
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        string combined = s + "#" + rev_s; // 添加分隔符避免重叠
       
        // 构建部分匹配表
        vector<int> pmt(combined.size(), 0);
        for (int i = 1, len = 0; i < combined.size(); ) {
            if (combined[i] == combined[len]) {
                pmt[i++] = ++len;
            } else {
                if (len > 0) {
                    len = pmt[len - 1];
                } else {
                    pmt[i++] = 0;
                }
            }
        }
       
        // 最长回文前缀长度
        int max_pal_len = pmt.back();
        // 需要添加的字符就是反转后的字符串去掉最长回文前缀的部分
        string to_add = rev_s.substr(0, rev_s.size() - max_pal_len);
        return to_add + s;
    }
};

五、示例分析

以输入"aacecaaa"为例：

1. 反转得到"aaacecaa"

2. 组合字符串："aacecaaa#aaacecaa"

3. PMT表最后一个值为7，表示最长回文前缀"aacecaa"

4. 需要添加"a"到前面，结果为"aaacecaaa"