思想
求最大回文字符串长度:manacher算法模版O(n)。
代码
import java.io.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static int manacher(String s){
StringBuilder str = new StringBuilder();
str.append('!');
for(int i=0; i<s.length(); i++){
str.append('#');
str.append(s.charAt(i));
}
str.append("#@");
int[] p = new int[str.length()]; //p[i]表示以i为回文中心的最大回文半径,这个数组只能在函数内部创建
int r = 0, c = 0, ans = 1; //r代表目前已经确定的回文字符串的右边界,c为回文中心
for(int i=1; i<str.length()-1; i++){
p[i]=i<r?Math.min(p[2*c-i], r-i):1;
while(str.charAt(i-p[i])==str.charAt(i+p[i])) p[i]++;
if(i+p[i]>r){
r = i+p[i];
c = i;
}
ans = Math.max(ans, p[i]-1); //自己更新的字符串的回文半径为p[i],原始字符串的回文半径为p[i]-1
}
return ans;
}
public static void main(String[] args)throws IOException{
out.println(manacher(in.readLine()));
out.flush();
out.close();
}
}