博文中会简要介绍Leetcode P0214题目分析及解题思路。
“Shortest Palindrome”这道题的全部意义只是为了考察KMP算法。
这里想吐槽一下，在面试环节想要当场手写
KMP算法其实比较困难，如果以准备面试为目标刷题的话，这道题其实写出O(n^2)的算法已经足够了。如果面试官要求写出KMP算法，那八成是在为难面试者。
其实这道题的基本思路很简单，就是在寻找回文串条件的最长的s[0:i]子串。O(n^2)的算法在正确性上没有问题，但是会超时，所以必须运用KMP算法来解题。具体解法本文不再详细阐述，但是代码还是附在了这篇博文上，使用的代码是Leetcode官方的解法。
Given a string s, you can 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.
以下是C++的题解代码实现。
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.length();
string rev(s);
reverse(rev.begin(), rev.end());
string s_new = s + "#" + rev;
int n_new = s_new.length();
vector<int> f(n_new, 0);
for (int i = 1; i < n_new; ++i) {
int t = f[i - 1];
while (t > 0 && s_new[i] != s_new[t])
t = f[t - 1];
if (s_new[i] == s_new[t])
++t;
f[i] = t;
}
return rev.substr(0, n - f[n_new - 1]) + s;
}
};