1.那就在每两个字符之间插入一个固定的字符，将字符串统统变为奇数长度的字符串
2.设置p数组，p[i]是以i为中心的最大对称半径
3.从左到右求p[]，id为之前的最长回文子串的中心，mx为回文串的边界
4.定义p[i]表示i位置的最长回文串长度，看下图，其中mx=p[id]，
假设当前要求的是p[i]，那么p[id]和p[j]都已经知道了，既然是回文串那么肯定是关于中心对称的，
（j的回文串被包含了，则i的回文串一定也被包含了）
5.j的回文串不被包含在最大的里面时，当p[j]>mx-i时，说明以i为中心的回文串可能延伸到mx外边，从mx+1处开始匹配，知道匹配失败以后，从而更新mx和p[i]
6.当i>mx时，则说明以i为中心的最长回文子串还没开始匹配寻找
因此需要一个一个进行匹配寻找，结束后更新mx和对应的id以及p[i]。
看到一份代码，看了半天才明白，算法很巧妙
把所有的情况都归到了前两种，不断更新已经处理到的最远位置，这样i永远不会大于mx，所以当对称点不满足时，只需要每次从mx+1的位置开始处理
代码：
class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() < 1)
return "";
String str = dealWithS(s); // 处理一下s,即将给字符串s的中间加上特殊字符，这样无论对于奇数字符还是偶数字符可以做同样的处理
int[] res = new int[str.length()];
int R = 0; // 当前所能扩展最大位置（最远的位置）
int C = 0; // C位置时最远能扩大到R
int maxC= 0; // 最长的半径的位置
res[0] = 0;
for(int i = 1; i < str.length(); i++)
{
int j = 2 * C - i; // i点的对称点
if(j >= 0 && res[j] < R - i) // 对称点存在且对称点的回文半径在C的回文中
{
res[i] = res[j];
}
else //如果j的回文串不被包含在回文的里面时,则从R+1开始扩展,这个算法把i>R的情况也进行了优化
{
int k = 1;
while(R + k < str.length() && 2 * i - R - k >= 0)
{
//当Len[j] >= sub.side - i时说明以S_new[i]为中心的回文串可能延伸到sub_side之外，而大于sub_side的部分还没有进行匹配，所以要从sub_side+1位置开始进行匹配，直到匹配失败以后，从而更新sub_side和对应的sub_midd以及Len[i]
if(str.charAt(R + k) == str.charAt(2 * i - R - k))
k ++;
else
break;
}
res[i] = R -i + k - 1;//半径
if(res[i] + i > R)//更新了R的位置，如果当前的i已经大于R了，那R也会更新到i的位置，R是最远可以达到的位置
{//所以每次只需要从R+1的位置开始匹配即可
R = res[i] + i;
C = i;
}
}
maxC = res[maxC] > res[i] ? maxC : i; // maxC保存的是回文半径最大的那个点的位置
}
String subStr = str.substring(maxC - res[maxC], maxC + res[maxC] + 1);
StringBuffer sb = new StringBuffer();
for(int i = 0; i < subStr.length(); i++)
{
if(subStr.charAt(i) != '#')
sb.append(subStr.charAt(i));
}
return sb.toString();
}
public static String dealWithS(String s) // 将原字符串进行处理
{
StringBuffer sb = new StringBuffer();
sb.append("#");
for(int i = 0; i < s.length (); i++)
{
sb.append(s.charAt(i));
sb.append("#");
}
return sb.toString();
}
}
网友评论