Shortest Palindrome(214 Hard)
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".
KMP实现
时间复制度O(n)
private static int[] getNextVal(String pattern) {
int pLen = pattern.length();
int[] next = new int[pLen];
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1) {
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
++j;
++k;
next[j] = k;
if (pattern.charAt(j) == pattern.charAt(k))
next[j] = next[k];
} else {
k = next[k];
}
}
return next;
}
public static int kmpMatch(String str, String pattern) {
int[] next = KMPSearch.getNextVal(pattern);
int i = 0;
int j = 0;
int sLen = str.length();
int pLen = pattern.length();
while (i < sLen && j < pLen) {
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || str.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
解题思路1：基于KMP
This problem asks us to add string before the input so the result string will be a palindrome. We can convert it to an alternative problem"find the longest palindrome substring starts from index 0". If we can get the length of such substring, then we can easily build a palindrome string by inserting the reverse part of substring after such substring before the original string.
public String shortestPalindrome(String s) {
if (s.length() <= 1)
return s;
char[] c_str = s.toCharArray();
// the next array stores the failure function of each position.
int[] next = new int[c_str.length];
next[0] = -1;
int i = -1, j = 0;
while (j < c_str.length-1) {
if (i == -1 || c_str[i] == c_str[j]) {
i ++;
j ++;
next[j] = i;
if (c_str[j] == c_str[i])
next[j] = next[i];
} else i = next[i];
}
//match the string with its reverse.
i = c_str.length - 1; j = 0;
while (i >= 0 && j < c_str.length) {
if (j == -1 || c_str[i] == c_str[j]) {
i --;
j ++;
} else {
j = next[j];
}
}
StringBuilder sb = new StringBuilder();
for (i = c_str.length-1; i >= j; i --) sb.append(c_str[i]);
for (char c : c_str) sb.append(c);
return sb.toString();
}