一.前言
对于回文串的处理方法有很多，还有中心扩展、哈希等方法。这里只是介绍两种我觉得有用的方法。这里的两种方法不针对的某一种特定题目，他们是一种解题思路，这两个算法像一个工具一样，在有需要的时候使用。
二.一维动态规划
首先介绍一下这个算法的作用，我们预处理出一个一维dp数组，时间复杂度是的，我们可以利用这个数组获得以 i 位置为结尾的最长回文串的起始位置。换句话说dp[i]存储的是一个下标。
下面找状态转移方程。
dp[i]的前面一个位置的 i-1 ，我们可以通过dp[i-1]来求出 i-1 位置的最长回文串的起始位置，我们首先要判断 i 与 dp[i-1]-1 位置的字符是否相同，如果相同，dp[i]=dp[i-1]-1。
如果不相等，那我们就要自行判断了。从dp[i-1]开始往后遍历，找到符合实际的起始位置。
下面是代码：
String str="aaabcbaba";
int n=str.length();
int[] dp=new int[n];
for (int i = 1; i < n; i++) {
if(dp[i-1]>0 && str.charAt(i)==str.charAt(dp[i-1]-1)){
dp[i]=dp[i-1]-1;
}else{
int left=dp[i-1];
int right=i;
int start=left;
while(left<right){
if(str.charAt(left)!=str.charAt(right)){
start=left+1;
right=i;
}else{
right--;
}
left++;
}
dp[i]=start;
}
}三.二维动态规划
在介绍这个算法之前先说明一下这个算法的作用。我们可以预处理出一个二维dp数组，时间复杂度是的，我们可以利用这个数组判断任意区间（子串）是不是回文串。虽然时间复杂度高，但是这个用途其实很广的，我们在做很多回文串的时候可以使用到这个。
下面说一下怎么做。
首先我们要定义一个boolean二维数组dp，dp[i][j]表示以 i 开始，以 j 结束的字串是不是回文串。这个也是我们的状态表示。下面根据这个状态表示写状态转移方程。
我们要得到dp[i][j]是不是回文串，先判断arr[i]==arr[j]，如果等于，那么dp[i+1][j-1]是true的话，dp[i][j]就是回文串。如果子串的长度是1或2（在arr[i]==arr[j]情况下），dp[i][j]直接置为true。
下面就是填表顺序，按照正常的填表顺序是不行的，我们可以发现，我们需要预先知道dp[i+1][j-1]的状态，因此要从下往上，从左往右遍历，并且我们只需要遍历一半的dp表就行了，因为这只是位置的标记，比如从2 开始到4结束，跟从4开始到2结束没什么区别。
为什么是这个遍历顺序？看看这个图就懂了。
下面这个就是代码了：
String s="aaabcbaba";
int n=s.length();
boolean[][] dp=new boolean[n][n];
for (int i = n-1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if(s.charAt(i)==s.charAt(j)){
dp[i][j]=i+1>j?dp[i + 1][j - 1]:true;
}
}
}预处理后的dp数组就是我们要的数组。
下面是例题，大家可以去这些例题中熟练这个技巧：
四.马拉车(Manacher)算法
我们在前面的方法处理回文串的时候其实都没有很好的利用回文串的性质。比如中心扩展方法，只是一味的利用对称的性质往外找，时间复杂度很高。我们是不是可以利用回文串对称的性质降低时间复杂度呢？马拉车(Manacher)算法就做到了这点。
马拉车(Manacher)算法可以的时间复杂度处理字符串，其处理出来的p数组内存储的值p[i]的以 i 中心的最长回文串的半径，最小是1，也就是半径包含其本身。
在正式介绍马拉车(Manacher)算法前，先说一下回文串的另一个特性，回文串有奇串和偶串，奇串是：bab这样的，偶串是：baab这样的。在使用中心扩展的方法时，我们要处理一遍奇串也要处理一遍偶串。在这里我们有一个方法可以解决这个问题：给每个字符之间加一个没有用的符号，像是#$^这样的，加完之后不管原来是奇还是偶都会变成奇的，不信大家可以自行验证。
这里还有一个问题要处理，如果有类似这种情况：#a#a#a#，我们处理的时候从中间的a不断往外扩展，这个时候就会有边界问题。我们可以在首尾加上一个不相等的字符，这样就可以规避掉这个问题了，像这样：$#a#a#a#^，到了边界自己就停了，这两个不相等的字符起到了哨兵的作用。
//预处理字符串例子
String str="aaabcbaba";
StringBuffer s=new StringBuffer();
s.append("$#");
for (int i = 0; i < str.length(); i++) {
s.append(str.charAt(i));
s.append("#");
}
s.append("^");
System.out.println(s);下面就是马拉车(Manacher)算法的核心部分了。
l 和 r 区间是一个回文串，mid是他们的中间位置（前面说了，我们预处理后的字符串肯定是奇串，所有一定是有中间位置的）。 i 是我们遍历到的下标， j 是 i 关于mid对称的下标， j = 2*mid-i。
我们是从前到后去枚举这个字符串，记录以i下标为中心的最长回文串的半径。对于上面这一张图，我们有一个前提是：j 下标位置我们已经处理过了，我们已经知道它的最长回文串半径是多少了（我们是从前往后枚举的）。
我们根据 i 得到 j 下标后，这里就根据 p[j] 分出了三种情况（前提是 i <= r）：
1）j - p[j] > l 或 i + p[j] < r
就是图上的这种情况，什么意思呢？我们知道，l r区间是回文串，mid又是中间位置，以 j 为中心的回文串（前提是符号本情况的范围），也是关于mid对称的，也就是说 i 的最长回文串半径也是这么大，即 p[i]=p[j]。
2）j - p[j] <= l 或 i + p[j] >= r
在这种情况下，我们就不能直接让 p[i]=p[j] 了。因为 j 的半径已经产出了 l 的范围，i 与 j 只是在 l 与 r 的区间内关于 mid 对称，超出 l 和 r 区间就不好使了。也就是图中蓝色的部分我们根本就不知道它是不是与绿色部分相同。
但是我们至少可以知道 p[i]最小是 r-i ，剩下的蓝色部分和前面的对不对称我们要使用中心扩展判断。
上面的内容其实是一个子问题，遍历到某一次时的情况，我们将这个子问题转成成代码时要注意最后要更新mid和r，如果 i+p[i] 的大小大于 r 的话，那我们要更新答案了，我们要利用新的回文串的特性。
//紧接上面的例子
int n=s.length();
int[] p=new int[n];
int mid=0;
int r=0;
for (int i = 1; i <= n-2; i++) {
int j=2*mid-i;
if(i<=r){
if(i+p[j]<r){
p[i]=p[j];
}else{
p[i]=r-i;
}
}
//使用中心扩展
while(s.charAt(i-p[i])==s.charAt(i+p[i])){
p[i]++;
}
//更新mid和r
if(r<i+p[i]){
r=i+p[i];
mid=i;
}
}这里要说一下，其实上面的代码也有问题，我们输出p数组就可以发现，这个里面还带着我们加的特殊字符#$^的回文半径，并且半径的大小也含有这些我们加的字符。但这些都无关紧要，没什么大不了的。我们这里只是介绍思想，在实际做题的时候情况复杂多变，到时候自己处理即可。这里给个最笨的办法处理：
for (int i = 2; i < p.length-1; i+=2) {
System.out.print(p[i]-1);
}在这个循环内大家可以自行修改得到每个位置的最长回文串半径。
如果大家还是不懂可以自己模拟一遍。
马拉车算法的经典应用：5. 最长回文子串（例题）
标签：int,Manacher,mid,算法,回文,我们,dp,拉车 From： https://blog.csdn.net/lllsure/article/details/143646018