好久没有刷题了，虽然参加过ACM，但是始终没有融会贯通，没有学个彻底。我干啥都是半吊子，一瓶子不满半瓶子晃荡。
就连简单的Manacher算法我也没有刷过，常常为岁月蹉跎而感到后悔。
问题描述
给定一个字符串s，求最长回文子串。
回文子串的回文指的是abccba这种从前往后读和从后往前读一样。
子串必须连续（比如从i到j，s[i:j]），不是最长子序列（最长回文子序列怎么求？），子序列是可以不连续的。
算法大意
ans[i]表示以字符i为中心的最长回文子串的长度
now表示now+ans[now]取得最大值的那个下标
对于当前字符i，如果i处在以now为中心的回文子串里，那么ans[i]的求法可以参考i关于now的对称点的回文子串长度，也就是ans[now-(i-now)].
例如：1j34now67i9，假设ans[j]=1,那么ans[i]也等于1，因为i和j都处在以now为中心的回文子串里面，它们是对称的。
上面所述即为算法关键，其余情形很容易自己想到。
但是Manacher算法用到了两个技巧
加#号，统一处理
ans[i]中记录的是以i为中心的最长回文子串，如果不作处理，这样只能够检测出长度为奇数的回文子串的最大长度。所以有一个巧妙的预处理。
给定字符串abcc，扩充成#a#b#c#c#。
a#b#a# 长度为3，以字符为中心的情况
a#a#a#a# 长度为4，以#为中心的情况
这样奇数偶数统一化处理。
首部加上一个怪异字符$,减少条件判断
如果在for循环中检测两个条件，那是很费事的，效率低。
如何判断一个条件有很多次无效的判断？就看这个条件发挥作用，影响程序分支的次数和进行条件求值的次数。
边界条件判断影响分支的次数很少，但却每次都要进行判断。
通过加上一个终止字符，就能够避免边界条件判断。
在Manacher算法中，要求回文子串同时要防止下标越界。所以直接在开头插入一个$字符，这样肯定因为失配而终止。
复杂度分析
Manacher算法为线性复杂度，因为从前往后有一个指针一直是单方向运动，没有回溯。
对于数组中的多个指针，如果都是单向运动，尽管它们运动的顺序和步长不同，那也一定是线性复杂度。
代码
#include<stdio.h>
#include<iostream>
using namespace std;
const int N = 110009;
char s[N];
char a[N * 2];
int ans[N * 2];
int now;
int main(){
freopen("in.txt", "r", stdin);
while (scanf("%s", s) != -1){
if (s[0] == 0)continue;
//#号法预处理
int j = 0;
a[j++] = '$';//这样就能少判断一点，不用考虑边界问题了
for (int i = 0; s[i]; i++){
a[j++] = '#';
a[j++] = s[i];
}
a[j++] = '#';
//开始算法主体部分
now = 1;
ans[0] = ans[1] = 0;
for (int i = 2; i < j; i++){
if (now + ans[now] < i){//如果当前字符不在阴影里，只能自力更生
int k = i;
while (a[k] == a[i - (k - i)]) k++;
ans[i] = k - i - 1;
now = i;
}
else{
int right = now - (i - now);
if (right - ans[right]>now - ans[now]){
ans[i] = ans[right];
}
else{
int k = now + ans[now];
while (a[k] == a[i - (k - i)])k++;
ans[i] = k - i - 1;
now = i;
}
}
}
//寻找答案，这部分可以直接放在求ans的过程中
int ma = 0;
for (int i = 1; i < j; i++){
if (ma < ans[i])ma = ans[i];
}
printf("%d
", ma);
}
return 0;
}
最长回文子序列
动态规划：复杂度都是O（n^2）
方法一：
a[i,j]表示s[i,j]之间最长回文子序列。则a[i,j]可以来自a[i+1,j-1],a[i-1,j],a[i,j-1].
方法二：
将s和s反过来得到的字符串求最长公共子序列