馬拉車(chē)算法用于求解最長(zhǎng)回文子串节芥。
說(shuō)明兩個(gè)概念：
R：回文串的半徑有滑。
C：回文中心。
步驟一：處理字符串壹士，將其字符間添加特殊字符#磷雇，用來(lái)消除奇偶的差異。
public static char[] change(String s){
char[] chars = new char[s.length()*2+1];
int i=0;
int index=0;
while(i<chars.length){
chars[i++]='#';
chars[i++]=s.charAt(index++);
}
return chars;
}
image.png
public static int manacher(String s){
char[] chars =change(s);
int[] size= new int[chars.length];
int R=-1;
int C=-1;
int max=Integer.MIN_VALUE;
for(int i=0;i<chars.length;i++){
size[i]=R>i?Math.min(size[2*C-i],R-i):1;//判斷是否超出邊界R
while(i+size[i]<chars.length&&i-size[i]>=0&&chars[i+size[i]]==chars[i-size[i]]){
size[i]++;
}//暴力求解
if(size[i]+i>R){
C=i;
R=size[i]+i;
}//更新R和C
max=Math.max(max,size[i]);//更新最大值
}
return max;
}
