马拉车算法是用来查找回文串的线性方法。
回文串是什么呢？
回文串是一种正反读都一样的字符串，比如bob noon 等都是回文字符串
如何在一个字符串中找出最长回文子字符串呢？
在上一篇的动态规划中就有这样的方法
当时是这样做的,创建一个boolean dp数组，表示从i 到 j的字符串是否回文
状态转义方程
如果 s[i] == s[j]
dp[i][j] == dp[i + 1][j - 1];
否则直接为false
初始状态
dp[i][i] 直接为 true
dp[i][i+1]需要循环判断值是否相等
随后 i从末尾，j从头部直接双循环遍历，即可得出结果
在马拉车算法中 首先对字符串做预处理，防止对字符串的奇偶性进行讨论，首先在字符串的首尾和每个字符之间加上#符号，这样我们的字符串长度如果原来为n 现在变为2n+1 必然为奇数
然后我们如果找到了回文串，还要定位到回文串的长度和下标，这样才能截取这个回文串
比如字符串bob
处理之后变为 #b#o#b#
那么处理之后，这个回文串的半径为4，实际长度为3
回文串的长度为半径-1
这个结论得出也很简单，因为处理后回文串的长度为2n+1,那么半径长度为n+1,原字符串长度为n，自然回文串的长度为新回文串半径-1
光知道长度还不够，现在必须知道这个字符串的在原来串中的起始位置
现在b在bob中的索引为0，那么如何定位到这个0呢
我们设bob字符串的长度为n处理后字符串的长度为2n+1,中心点o的位置为n，半径为n+1
如果字符串为moom
处理后为#m#o#o#m#
m为moom的索引为0，处理后字符串为2n+1， 处理后半径n+1 中心点位置还是n
我们发现中心点位置 + 1 减去半径则为0，但是如果是其他字符串
ex 122122
处理后 #1#2#2#1#2#2#
如果其半径为n，中心位置下标随着前置元素的增加而往后移动
所以只能为中心位置 - 半径，但是上述两者均为-1
那么处理字符串的时候在前面加上一个不会被用到的特殊字符$
加上后，处理后字符串的中心下标+1，那么n + 1 - n -1 = 0，而且前面每加上一个非回文元素，中心下标会+2，原字符串只能+1,所以这里要除以2
那么原回文串起始下标为(处理后回文串中心位置 - 处理后回文串半径)/2
这一行代码是马拉车算法核心点
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
对i进行计算，mx为现有所有回文串的最右侧
如果 mx > i
另 2* id - i = j 那么j为i关于id的对称点，
如果j的半径p[j] 在当前p[id]内部，那么 ij关于id堆成，那么p[i]也必然在mx内部，所以有p[i] = p[j]
如果j的半径p[j] 超过mx对称点，那么不知道mx对称点左侧和右侧是否对称，所以只能将值暂时设置为
mx - i 然后剩下的挨个计算
如果mx < i 也就是之前的回文右端都不超过mx，并且最右端的元素p[mx] = 1 时，只能定义p[i] = 1
对接下来的元素挨个计算；
代码部分
public String malache(String s){
//首先处理字符串
String t = "$#";
for (int i = 0; i < s.length(); i++){
t += s.charAt(i);
t += "#";
}
t += "~";
//设置3个值
int id = 0; //马拉车算式中的id
int returnLength = 0 ;// 最常子串的长度
int returnIndex = 0;// 最长子串的起始索引
int mx = 0;
int [] p = new int[t.length()];
for (int i = 0; i < t.length(); i ++){
// 马拉车算法
p[i] =mx > i ? Math.min(p[2 * id - i], mx - i):1;
while (p[i] + i< t.length() && i - p[i] >=0 && t.charAt(i + p[i]) == t.charAt(i - p[i])){ //挨个计算值,边界条件计算
p[i] += 1;
}
if (mx < p[i] + i){ //刷新id
mx = i + p[i];
id = i;
}
if(returnLength < (p[i] - 1)){
returnLength = p[i] - 1;
returnIndex = (i - p[i])/2;
}
}
return s.substring(returnIndex,returnIndex + returnLength);
}
