题目：
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.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
链接： http://leetcode.com/problems/shortest-palindrome/
题解：
KMP ? Manacher ? Suffix Array?
猜想 - 找到以s.charAt(0)开始的最长的palindrome，然后再用s.length()减去这个长度，就是我们需要添加的字符长度。这时候我们再在原String之前添加就可以了。
假设s = "bcba"，那么以s.charAt(0)为左边界的longest palindrome是"bcb"，需要添加的是"a"，返回"abcba"。
假设s = "bba"，那么以s.charAt(0)为左边界的longest palindrome是"bb"，需要添加的是"a"，返回"abba"。
假设s = "bcd"，那么以s.charAt(0)为左边界的longest palindrome长度为"b"，需要添加的是"cd"，返回"dcbcd"。
这样把问题转化为求以s.charAt(0)为起点的longest palindrome问题。 接下来就是coding了，应该可以用Manacher或者KMP在O(n)解决，晚上回家再试写。 假如不是只在左边添加，而是哪里都可以插入的话，那么就和Edit Distance很像，应该能够用DP解决。
又查了查，好像有些类似的问题叫做palindrome prefix。
Manacher:
稍微修改了一下自己在5. Longest Palindromic Substring的代码，最后求出P的时候，计算一下最长的prefix就可以了，代码略繁琐，二刷要好好再简化。
Time Complexity - O(n)， Space Complexity - O(n)。
public class Solution {
private String s;
private char[] t;
private int[] p;
public String shortestPalindrome(String s) {
if(s == null || s.length() <= 1)
return s;
this.s = s;
preprocess();
p = new int[t.length];
int center = 0, right = 0;
for(int i = 1; i < t.length - 1; i++) {
int mirror = 2 * center - i;
if(right > i)
p[i] = Math.min(right - i, p[mirror]);
while(i - p[i] >= 0 && i + p[i] < p.length && t[i + p[i]] == t[i - p[i]]) //try to expand
p[i]++;
if(i + p[i] > right){
center = i;
right = i + p[i];
}
}
center = 0;
for(int i = 1; i < p.length - 1; i++) {
if(p[i] == i + 1)
center = i;
}
return new StringBuilder(s.substring((center + p[center]) / 2)).reverse().toString() + s;
}
private void preprocess() {
t = new char[s.length() * 2 + 1];
for(int i = 0; i < s.length(); i++) {
t[2 * i] = '#';
t[2 * i + 1] = s.charAt(i);
}
t[t.length - 1] = '#';
}
}
KMP:
对于这道题目， KMP应该是更容易想到的方法才对。因为这里要求longest palindrome prefix，和KMP的预处理步骤，求Pattern P的Prefix table几乎一模一样。下面我们用KMP来求解。
下面的解法是Discuss里的，先拿过来再研究。自己其实还没有想透。
public class Solution {
public String shortestPalindrome(String s){
String s_reverse = new StringBuilder(s).reverse().toString();
String str = s + "." + s_reverse;
int[] size = new int[str.length()];
for(int i = 1; i < str.length(); i++){
int temp = size[i - 1];
while(temp != 0 && str.charAt(temp) != str.charAt(i))
temp = size[temp - 1];
if(str.charAt(temp) == str.charAt(i))
temp++;
size[i] = temp;
}
return s_reverse.substring(0, s.length() - size[str.length() - 1]) + s;
}
}
Suffix Array: (未成功， 还没想好，需要修改)
有O(n)的构建方法，不过比较难写出来。现在做不到用Suffix Array来解这道题目其实是因为知识和理解的不够，弱爆了唉...
public class Solution {
public String shortestPalindrome(String s) {
String t = new StringBuilder(s).reverse().toString();
String[] sPrefixArray = getPrefixArray(s);
String[] tSuffixArray = getSuffixArray(t);
int max = 0;
for(int i = 0; i < s.length(); i++) {
if(sPrefixArray[i].equals(tSuffixArray[i]))
max = i;
}
return new StringBuilder(s.substring(max)).reverse().toString() + s;
}
private String[] getPrefixArray(String s) {
int N = s.length();
String[] res = new String[N];
for(int i = 0; i < N; i++) {
res[i] = s.substring(0, i + 1);
}
return res;
}
private String[] getSuffixArray(String s) {
int N = s.length();
String[] res = new String[N];
for(int i = N - 1; i >= 0; i--) {
res[N - 1 - i] = s.substring(i);
}
return res;
}
}
递归双指针对向遍历:
在Discuss终于发现了神解法。 来自这个帖子 - https://leetcode.com/discuss/51223/my-7-lines-recursive-java-solution . 主要使用两个指针从前后对向遍历，就跟我们判断String是否是Palindrome一样，假如s.charAt(i) == s.charAt(j)，则j++。走完之后的结果j所在假如是s.length() - 1，则整个String为Palindrome，返回s，否则，j所在的位置及其以后的部分肯定不是Palindrome，这是我们要把这部分翻转并且加到结果的前面。至于 substring(0, j)这部分，我们仍需要使用递归的方法继续判断。非常非常巧妙。其实一开始思考求以s.charAt(0)为起点的方法时，觉得应该有方法可以不用KMP，Manacher，Rabin-Karp等等String Match的方法，这下终于见到了。真厉害。
Time Complexity - O(n)， Space Complexity - O(n)
public class Solution {
public String shortestPalindrome(String s){
int j = 0;
for (int i = s.length() - 1; i >= 0; i--)
if (s.charAt(i) == s.charAt(j))
j += 1;
if (j == s.length())
return s;
String suffix = s.substring(j);
return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;
}
}
题外话:
下午表哥正好在WTC附近开会，中午和同事们吃饭的时候接到他的电话，赶紧过去聚一聚。聊天中谈到打算换工作的事情，表哥说他不太懂计算机这行，但现在公司看中的不是背题背概念，重要的还是思维和解决问题的能力。他说得很对。拿到问题，如何思考，如何解决，怎样把问题抽象成为数学模型，计算机模型等等，这方面我都要好好加强。以后也许有机会的话还要学一学统计方面的知识，和MBA方面的知识。快速学习的能力也很重要，现在新技术新概念层出不穷，要有快速接受，学习，吸收的能力才行。
Reference:
http://www.cnblogs.com/grandyang/p/4523624.html
http://problem-solving-notes.blogspot.com/2010/11/one-solution-of-palindromic-prefix.html
http://*.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree
http://algo2006.csie.dyu.edu.tw/paper/2/A24.pdf
https://www.youtube.com/watch?v=5i7oKodCRJo
https://web.stanford.edu/class/cs97si/10-string-algorithms.pdf
http://www.nayuki.io/page/knuth-morris-pratt-string-matching
https://leetcode.com/discuss/64309/clean-kmp-solution-with-super-detailed-explanation
https://leetcode.com/discuss/51223/my-7-lines-recursive-java-solution
https://leetcode.com/discuss/52564/a-kmp-based-java-solution-with-explanation
https://leetcode.com/discuss/questions/oj/shortest-palindrome?start=0
https://leetcode.com/discuss/36833/java-ac-code-may-help-u-another-need-more-test-cases