题目

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1：

输入：s = "aacecaaa"
输出："aaacecaaa"

示例 2：

输入：s = "abcd"
输出："dcbabcd"

提示：

  • 0 <= s.length <= 5 * 104
  • s 仅由小写英文字母组成

解答

  • KMP算法求解

本题可以通过将原字符串翻转后与原字符串拼接，然后在新的字符串中找到以原字符串开头的最长回文子串，最后将翻转字符串的前缀加到原字符串前面即可得到新的字符串。为了找到以原字符串开头的最长回文子串，可以使用KMP算法中的next数组，将新的字符串l的next数组求出来，那么l.size() - 1位置处的值就是以原字符串开头的最长回文子串的长度。

class Solution {
public:
    string shortestPalindrome(string s) {
        // 将字符串s翻转并存储在rev_s中
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        // 将s和rev_s拼接，并用“#”分割
        string l = s + "#" + rev_s;
        // 初始化一个大小为l.size()的数组p
        vector<int> p(l.size(), 0);
        // 通过循环遍历l，求出p数组
        for (int i = 1; i < l.size(); i++) {
            int j = p[i - 1];
            while (j > 0 && l[i] != l[j]) j = p[j - 1];
            p[i] = (j += l[i] == l[j]);
        }
        // 返回一个由rev_s的前缀和s组成的新字符串
        return rev_s.substr(0, s.size() - p[l.size() - 1]) + s;
    }
};

以输入s="aacecaaa"为例，说明代码的运行过程：

首先将字符串s翻转得到rev_s=”aaacecaa”，然后将s和rev_s用”#”分割拼接起来得到l=”aacecaaa#aaacecaa”。

然后初始化一个大小为l.size()的数组p，数组中每个元素表示对应位置之前的字符串的最长相同前缀后缀的长度。

接下来使用KMP算法的思想，通过遍历l来求得数组p的所有元素。从i=1开始，依次比较l[i]和l[p[i-1]]，如果不相同，则令j=p[i-1]，并循环将j更新为p[j-1]，直到j=0或者找到一个位置k使得l[i]和l[k]相等。如果找到了k，则令p[i]=k+1，否则令p[i]=0。

经过上述循环遍历后，p数组的最后一个元素p[l.size()-1]表示以原字符串开头的最长回文子串的长度，即3。因此，可以将rev_s的前缀”aa”加到s的前面，得到新的字符串为”aaacecaaa”，这个字符串是由原字符串”aacecaaa”通过添加最少字符得到的回文串。