Manacher算法
问题描述
- Manacher算法解决的问题：
（1）字符串str中，最长回文子串的长度如何求解
（2）如何做到时间复杂度O(N)完成？
常规思路
- 遍历每个字符，将每个字符看成一个中心（对称轴），分别向左右扩展，相同就继续扩展，不同就结束
- 缺点：偶数个字符的回文，中心（对称轴）不是单个字符，会被忽略
- 解决技巧：处理长度为n的字符时，在原字符的空隙之间添加特殊字符，此时偶数个字符的回文以可转化成奇数个的去解决
- 例：
（1）原字符：1 2 2 1 3 1 2 2 1 若统计1 2 2 1 就会出现忽略
（2）添加特殊字符：# 1 # 2 # 2 # 1 # 3 # 1 # 2 # 2 # 1 # ，此时的回文均为奇数个，便都可以进行统计 - 统计出最长的回文，因为添加了特殊字符，所以结果除以2后向下取整，便是答案
- 特殊字符的选择：特殊字符可以是任意的，就算是原字符中出现过的也可以，因为其实每次比较是都是原来字符之间比较，新填的字符之间比较，所以特殊字符的选择不影响记录
- 时间复杂度O(N ^ 2)，N为字符个数
Manacher思路
- Manacher与kmp类似均是在常规思路的基础上进行加速
- 在常规思路添加特殊字符的基础上进行改进
- 基本概念：
（1）回文半径与回文直径：扩充区域的大小
（2）回文半径数组：记录每一个字符的回文半径
（3）回文右边界：int型，初始值为 -1， 右扩的过程中能达到的最右边界的后一个位置
（4）回文中心点：int型，初始值为 -1， 右扩的过程中达到的最右边界时，中心点的下标
（5）回文右边界与中心点是一起使用的，同时进行更新 - 情况分析：
（1）当前点 i 不在回文右边界里：暴力扩充，无优化，直接扩
（2）当前点 i 在回文右边界里：
L：左边界，R：右边界，C：中心点，i‘ ：i 关于C的对称点
在回文半径数组中可以得到，i’ 的回文情况
(a ) i’ 的回文区域在L内部，则 i 的回文半径就是 i‘ 的回文半径
(b ) i’ 的回文区域有一部分已经在L外部，那么 i 的回文半径就是 i 到 R的部分
(c ) i‘ 的回文区域与L重合，i 的回文半径一定 >= i 到 R 的部分，需要对R 后的东西与R关于 i 的对称点 R’ 进行比较，判断回文区域 - 时间复杂度O(N)，N为字符个数
代码实现
- 若使用情况分析的结果挨个判断实现代码太过繁琐
- 可以整合无需判断回文的部分，得到对应的回文半径后，跳过无需判断的部分后，剩余代码部分情况全部判断是否能扩张
（1）情况1，无需比较的部分就是自己回文半径从1开始
（2）情况2，a的情况是最小值，b与c都是基于回文右边界 - i，则比较preArr[ i‘ ] 与 R - i + 1的大小，取较小值就是不用判断的部分
public static int manacher(String str){ if (str == null || str.length() == 0){ return 0; } char[] chs = manacherString(str); //添加特殊字符 int[] preArr = new int[chs.length]; //回文半径数组 int mid = -1; //回文中心 int R = -1; //回文右边界 int max = Integer.MIN_VALUE; //最大回文长度 for (int i = 0; i < chs.length; i++){ //遍历字符数组 //不用判断的区域 //i <= R当前点i不在右边界，回文半径至少是 1 //i在右边界的两种情况：i'的回文在 L内，或者L外i //通过对称点 i’ 或者 R - i中的最小值，就可判断时哪一种情况 preArr[i] = R > i ? Math.min(preArr[2 * mid - i], R - i + 1) : 1; while (i + preArr[i] < chs.length && i - preArr[i] > -1) { //不超过左右字符数组的情况下 //无论是哪一种情况都判断能否扩张，使得代码精简 if (chs[i + preArr[i]] == chs[i - preArr[i]]){ //满足扩展 preArr[i]++; }else { break; } } if (i + preArr[i] > R){ //更新R，mid R = i + preArr[i] - 1; mid = i; } max = Math.max(max, preArr[i]); } //原字符串是扩充串回文半径 - 1 return max - 1; } public static char[] manacherString(String str) { //添加特殊字符，使得回文字符的长度全部变成偶数 char[] strArr = str.toCharArray(); char[] chs = new char[str.length() * 2 + 1]; for (int i = 0, j = 0; i < chs.length; i++){ //偶数位置加入特殊字符 chs[i] = (i & 1) == 0 ? '#' : strArr[j++]; } return chs; }
