Leetcode - Shortest Palindrome

My code:

public class Solution {
    public String shortestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        
        String t = s + "#" + new StringBuilder(s).reverse().toString();
        int[] dp = new int[t.length() + 1];
        int j = 0;
        int k = -1;
        dp[0] = -1;
        while (j < dp.length - 1) {
            if (k == -1 || t.charAt(k) == t.charAt(j)) {
                k++;
                j++;
                dp[j] = k;
            }
            else {
                k = dp[k];
            }
        }
        
        StringBuilder sb = new StringBuilder(s.substring(dp[dp.length - 1]));
        return sb.reverse().toString() + s;
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        String ret = test.shortestPalindrome("ababbbabbaba");
        System.out.println(ret);
    }
}

reference:
https://discuss.leetcode.com/topic/27261/clean-kmp-solution-with-super-detailed-explanation/2

这道题目搞了很久。终于看了答案自己写了出来。
首先做了下 implement strStr() 题，复习了下 KMP算法
终于记起来怎么写了，希望下次不要忘记。。。

然后这道题目，可以继续抽象。
找到 以 index = 0 开头的substring，是最长的palindrome
找到之后，将剩余的部分反转，加在前面，就行了。

下面的问题是，如果找到这个最长的palindrome.

brute-force: O(n ^ 2) TLE
但是仍然佩服，能够走到这一步的人。这是思维的力量。即使没做出来，这道题目的意义，已经达到了。

如何在 O(n) 找到他呢？
构造一个 string:
s + "#" + reverse(s)
为什么需要这个 #
强行隔开两个string

如果 [0, k] match [j, j + k]
k >= s.length() && j < s.length()
之后将这个字符串取出来。
s.substring(0, k + 1) 就会越界。因为 s 的指针都跑到reverse(s) 去找匹配了，并且还找到了，导致长度比实际长度还要长。
所以我们需要用 # 强行隔开两者。

其次，利用KMP 构造 next 数组。
这里，有两个注意点：
1 . dp length 应该等于 s.length + 1
也就是多一位，用来衡量 [0, len - 1] 的情况。和KMP略有不同
2 . 我们只关注dp最后一位的情况。因为它包含的是，s 以0开头，最长的panlindrome 的长度。

| ------> | # | <------ |
012345 543210
所以如果 dp[len - 1] = 2
表示，有两位 prefix match with postfix
即， s[0, 1] 是最长回文字符串。
然后我们拿到这个长度，把之后的string拿出来reverse，加在前面。
这道题目就解决了。

差不多就这样了。

KMP 文章：
http://blog.csdn.net/v_july_v/article/details/7041827

Anyway, Good luck, Richardo! -- 09/20/2016