上一篇KMP算法之后好几天都没有更新，今天介绍最长回文子串。
首先介绍一下什么叫回文串，就是正着读和倒着读的字符顺序都是一样的，eg:level，noon。而回文子串，顾名思义，就是主串中满足回文性质的子串。
求解的常规思想，就是先求出主串的所有子串，在判断是否是回文串，然后选出最长的，这一种方法的时候复杂度较高，是O(n^3)，所以一般不采用这种方法，下面介绍两种方法求解。
1. 中心扩展法
中心扩展法可以说是常规算法的改进。首先我们知道，回文串是中心对称的，相比从头到尾遍历字符串的方法，从中间开始向两边扩展，时间会减少一半。
算法思想：把主串中的每一个字符当做回文串的中心，向两边扩展，求出最长的回文子串。其中要注意奇数位的回文子串和偶数位的回文子串的区别。eg:aba的中心是b，而abba的中心应该是bb。使用中心扩展法的时间复杂度是O(n^2)，空间复杂度是O(1)。
代码
核心算法是l2r的部分，以传入的mid为回文串的中心计算最长的回文子串，其中需要注意的地方有两点：
l2r中的第一个while循环，之前提到过要注意奇数位的回文串和偶数位的回文串，在代码中，判断中心点的字符和右边的字符是否相等，就可以跳过偶数位的中心点。
注意l2r中返回语句，从第二个while循环中跳出的时候，已经多进行了一步left--，right++的操作了。
int longest;//子串长
int start;//最长回文子串在主串中的起始位置
/*计算以mid为中心的最长回文子串*/
int l2r(char *string, int mid) {
int len = strlen(string);
int left = mid - 1, right = mid + 1;
//跳过相同的部分
while (string[right] == string[mid])
right++;
while (left > 0 && right < len){
if (string[left] == string[right]) {
//从中间开始算，各向外移一位
start = left;
left--;
right++;
}
else {
break;
}
}
//重置回文串的起始位置
if (left < 0)
start = 0;
//printf("\tstart:%d left:%d right:%d len:%d\n", start, left, right, right - 1 - (left + 1) + 1);
//跳出while循环的时候，要么是index不满足条件，要么是当前right和left的位置字符不等，都要在将right,left还原成删一个状态才能计算回文串长
return right - 1 - (left + 1) + 1;
}
/*计算最长回文子串的长度*/
int longestPald(char *string) {
int len = strlen(string);
if (string == NULL || len == 0)
assert("ERROR");
if (len == 1){
longest = 1;
start = 0;
return 1;
}
for (int i = 0; i < len; i++){//遍历整个主串，以它的每一位为回文串的中心，计算最长的回文串
int tempLen = l2r(string, i);
if (tempLen > longest) {
longest = tempLen;
}
}
return 0;
}
int main(void)
{
char string[] = "abcdeedcbdac";
longestPald(string);
printf("\t%s的最长回文子串:\n", string);
printf("\t起始位置：%d 串长：%d\n", start, longest);
system("pause");
return 0;
}
结果：
2. 动态规划法？？？
之前看到网上有很多用动态规划法求解最长回文子串的，但是我看了之后觉得有问题。动态规划法中是用二维矩阵保存回文串长，c[i][j]表示主串中s[i...j]是回文串，当前位置的c[i][j]需要依赖于c[i+1][j-1]，但是有的地方c[i+1][j-1]是不知道的，反而觉得用递归来计算矩阵c会更好。不知道是我理解错误还是这个方法确实不对。如果有用动态规划法求解出最长回文子串的，还请赐教~
3. Manacher算法
这是几个方法中最为高效的方法，时间复杂度为O(n).Manacher算法也是利用回文串的对称性，标记回文串的中间位，向两边遍历。同样是标记中间位，向两边遍历，那它和中心扩展法有什么区别呢？
区别：中心扩展法的思想是以主串的每一个字符为中心，计算最长的回文子串，外层循环执行n次，内存循环至多2/n次；而Manacher的中心字符并不是这样的，Manacher利用之前计算过的回文子串，巧妙的计算出新的中心点。但同时它也做出了一些折中的处理，比如说，要确定唯一的中心点，所以要扩展主串。
算法思想：Manacher采用从中间向两边遍历得到最长回文子串的思想，将原来的主串进行扩展，这个算法严格要求对称，只允许有一个中心点。eg:abc-- > #a#b#c#，这样不管回文串是奇数位还是偶数位都都会变成奇数位的，满足只有一个中心字符的要求。Manacher利用之前计算的回文子串，避免了一些重复的回文子串的计算。
辅助变量：
既然要利用之前求得信息，就需要记录。
p[]:数组p保存的是主串中以某个字符为中心的最长回文子串的半径，eg：p[i]存储的是以str[i]为中心的最长回文串的半径，这个半径值是在扩展之后的字符串中。
mid:保存得到的回文串的中心点。
max:保存当前的回文串的影响范围，也就是这个回文串的右边界。
注：mid和max的值是由最长回文串计算得到的。
现在，我们来看一下str和p的关系，便于理解。s是在原来的字符串
接下来计算p[],这时要用到max和mid。先解释一下最难懂的地方。利用之前计算的回文子串的信息计算当前的p[i]，现则最小的值。
p[i] = (max - i) > p[j] ? p[j] : (max-i);
解释：（以下解释摘自另一篇博客）
1.当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。
2.当 P[j] > mx - i 的时候，以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能一个一个匹配了。
接下来解释算法为线性的原因：（算法中其实有两层循环）
代码：
代码中有几个需要注意的地方：
- 在pre函数中，扩展主串时，扩展串的第一个位置是'$'，这是为了诸侯方便处理越界的问题。而字符串越界会出现在哪里呢？就是manacher中的为一个一个while循环那里。
- 注意重置longest和start时候的值，在介绍str和p的关系的时候已经提到过p[i]-1的意义，在设置longest和start时要考虑到这个关系。（longest是最长回文子串的长度，start是其在原串中的下标）。
- 理解p[i] = (max - i) > p[j] ? p[j] : (max-i);很重要，结合代码中的注释和上面的图多理解。
int pre(char *string, char *strCopy) {
strCopy[0] = '$';
int j = 1;
for (int i = 0; i < strlen(string); i++) {
strCopy[j++] = '#';
strCopy[j++] = string[i];
}
strCopy[j] = '#';
return j + 1;//表示strCopy的长度
}
void manacher(char *str,int n) {
int p[MAXLEN];//数组p中保存字符串str中以某一点为中心点的最长回文子串的半径
p[0] = 0;//p[0]对应str[0]-->$
//max存储之前计算的回文子串的右边界，mid保存当前的回文子串的中心,这两个值都不一定是最长回文子串求得
int max = 0, mid = 1;
for (int i = 1; i < n; i++) {
if (max > i)
{
int j = 2 * mid - i;//j是字符串中i关于mid的对称点
p[i] = (max - i) > p[j] ? p[j] : (max - i);//!!!
}
else {//否则max<i,说明i不包含在当前计算的回文串中，
//那么就不能用便捷方法来计算p[i]，只能一个一个计算
p[i] = 1;//初始值为1
}
//基于当前以i为中心的回文串的半径，计算下一个位置的字符是否满足回文。这里会出现越界的问题！！！
while (str[i - p[i]] == str[i + p[i]]){
p[i]++;
}
if ((i + p[i]) > max){
max = i + p[i];//当前计算得到的回文串已经大于之前计算的边界了，重置边界
mid = i;
}
if (longest < p[i] - 1){//p[i]-1就是原串中以i为中心的回文串的长度
longest = p[i] - 1;
//在遇到最长回文子串包含第0个字符的时候，start计算得-1，所以这里要处理一下
if ((i - p[i] - 1) < 0)
start = 0;
else
start = i - p[i] - 1;
}
}
}
int main(void)
{
char string[] = "acab";//"abcdeedcbdac";
char strCopy[MAXLEN];
int len = pre(string, strCopy);
printf("原串：%s -->", string);
//输出strCopy
for (int i = 0; i < len; i++){
printf("%c", strCopy[i]);
}
printf("\n");
manacher(strCopy,len);
printf("\t%s的最长回文子串:\n", string);
printf("\t起始位置：%d 串长：%d\n", start, longest);
system("pause");
return 0;
}
结果：
总结
好了，这次就到这里了。不足之处，欢迎指正。
