CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目
214. Shortest Palindrome
难度困难205
Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
Example 1:
Input: "aacecaaa"
Output: "aaacecaaa"
Example 2:
Input: "abcd"
Output: "dcbabcd"
解法
解法一
又是字符串，又是回文串的问题……关键是这题是怎么思考的？最短的回文串 =》 最长的回文子串 =》如何快速判断一个字符串是不是回文串 =》字符串哈希 =》 字符串哈希可以从上一步O(1) 得到，所以得到了一个 O(n) 的算法。算法如下：
class Solution {
public:
string shortestPalindrome(string s){
typedef long long LL;
int base = 173;
int mod = 1000000007;
LL val = 0;
LL rev_val = 0;
int res = 0;
LL power = 1;
for(int i=0;i<s.length();++i){
val = (val*base % mod + int(s[i]))%mod;
rev_val = (rev_val + (int)(s[i]) * power )%mod;
power = power * base % mod;
if(val == rev_val){
res = i;
}
}
res = s.length() -1 - res;
string ans;
for(int i=0;i<res; ++i){
ans.push_back(s[s.length()-1-i]);
}
ans = ans + s;
return ans;
}
};
解法二
KMP 算法思考此题。如上面分析的那样，要寻找一个最长的回文子串？什么意思呢？等价于寻找 s 的一个逆字符串 s’，并在其中寻找一个最长匹配！！！
这就是 KMP 算法可以直接解决的。