一、Manacher算法、
代码语言：javascript复制public static char[] mannacherString( String str){
char[] charArr = str.toCharArray();
char[] res = new char[str.length()*2 1];
int index = 0;
for (int i = 0;i<res.length;i ){ // 偶数的位置设为 #
res[i] = (i&1) == 0 ? '#':charArr[index ];
}
return res;
}
public static int maxLcpsLength(String str) {
if (str == null || str.length() == 0){
return 0;
}
char[] charArr = mannacherString(str);
int[] pArr = new int[charArr.length];
int index = -1;
int pR = -1;
int max = Integer.MIN_VALUE;
for (int i = 0;i != charArr.length;i ){
pArr[i] = pR > i ? Math.min(pArr[2 * index - i],pR - i) :1;
while (i pArr[i] < charArr.length && i - pArr[i] > -1){
if (charArr[i pArr[i]] == charArr[i - pArr[i]]){
pArr[i] ;
}else break;
}
if ( i pArr[i] > pR){
pR = i pArr[i];
index = i;
}
max = Math.max(max,pArr[i]);
}
return max - 1;
}
二、214.Shortest Palindrome
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:
代码语言：javascript复制Input: "aacecaaa"
Output: "aaacecaaa"Example 2:
代码语言：javascript复制Input: "abcd"
Output: "dcbabcd"解法：
代码语言：javascript复制public static char[] manacherStr(String str){
char [] chars = str.toCharArray();
char [] res = new char[str.length()*2 1];
for (int i = 0 ; i < res.length;i ){
res[i] = (i & 1) == 0 ? '#': chars[i/2];
}
return res;
}
public static String shortestPalindrome(String s) {
if (s == null || s.length() < 2) return s;
StringBuffer stringBuffer = new StringBuffer(s);
stringBuffer.reverse();
String revStr = new String(stringBuffer);
char[] chars = manacherStr(revStr);
System.out.println(chars);
int pArr [] = new int[chars.length];
int pR = -1;
int index = -1;
int maxContainEnd = -1;
for ( int i = 0 ;i < pArr.length;i ){
pArr[i] = (pR > i) ? Math.min(pR - i ,pArr[ 2 * index - i]):1;
while ( i pArr[i] < pArr.length && i - pArr[i] >=0){
if (chars[i pArr[i]] == chars[ i - pArr[i]]){
pArr[i] ;
}else break;
}
if ( i pArr[i] > pR){
pR = i pArr[i];
index = i;
}
if (pR == chars.length){
maxContainEnd = pArr[i];
break;
}
}
StringBuffer stringBuffer1 = new StringBuffer(revStr);
for (int i = (pArr.length -(2 * maxContainEnd - 1)) /2 - 1; i >= 0;i--){
stringBuffer1.append(stringBuffer1.charAt(i));
}
return String.valueOf(stringBuffer1);
}
