端午安康~
好久没写算法类文章了。这个假期出行计划泡了汤，没太多事情做，随便搞一篇吧。
最长回文子串
所谓最长回文子串（longest palindromic substring, LPS），顾名思义就是指一个字符串中，长度最大且又满足回文性质的连续子串。例如："bananas"的最长回文子串是"anana"，"麻麻说上海自来水来自海上"的最长回文子串是"上海自来水来自海上"。
求解最长回文子串是一类有趣的算法问题。本文先介绍比较朴素且容易实现的中心扩展法，再介绍由中心扩展思想改进而来的Manacher算法。
中心扩展法
回文串正着读和反着读是一样的，所以一定会有一个对称中心。因此，naive solution就是在原串中逐个枚举对称中心点，同时向左、向右扩展，并比较左右两侧的字符是否相等，最终取出长度最大的那个即可。
需要注意的是，当回文串长度为奇数时，对称中心是具体的字符，如下图。
但是当回文串长度为偶数时，对称中心会位于两个字符的间隙，如下图所示。
由于我们事先无法确定最长回文子串的长度奇偶性，所以每次扩展都要取两次中心点，再取两者的扩展结果中长度较大的那个。代码如下，比较容易理解。
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int h = 0, t = 0;
for (int i = 0; i < s.length(); i++) {
int l1 = expand(s, i, i); // 以字符作为中心点扩展
int l2 = expand(s, i, i + 1); // 以字符间隙作为中心点扩展
int pl = Math.max(l1, l2);
if (pl > t - h) { // 由当前的LPS长度推出下标范围
h = i - (pl - 1) / 2;
t = i + pl / 2;
}
}
return s.substring(h, t + 1);
}
private int expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return r - l - 1;
}
}
显然，中心扩展法的时间复杂度为O(n2)，空间复杂度为O(1)。
Manacher算法
O(n2)的时间复杂度显然不尽如人意。所以在1975年，Manacher提出了一个线性时间复杂度的新算法。该算法狠精妙，下面详细讲解之。
预处理
为了解决偶数长度回文串的对称中心在字符间隙的问题，我们在原字符串每个字符前后都插入原本不存在的分隔符（例如"#"或"|"）。这样，带分隔符的字符串长度就固定为奇数（2n+1）了，不必再考虑字符间隙，并且没有破坏回文子串的对称性。
挖掘对称性
考虑字符串"|a|b|a|a|b|a|"，如果我们按照上述中心扩展法来计算，可以得到下图的结果。
其中，position是各字符的下标，LPS Length则是带分隔符的串中，以各个字符作为中心的回文子串的“半径”（包含中心本身以及除了开头和结尾外的"|"符号）。由于"|"符号也是对称的，所以LPS Length恰好等价于去掉"|"符号之后，原字符串以各位置为中心的回文子串的长度。Manacher算法就是致力于找到LPS Length最大的那个点。
如果我们将LPS Length视为以position为下标的数组lpsl[]，可以发现有以下规律：
- lpsl[6] = 6, lpsl[5] = lpsl[7] = 1, lpsl[4] = lpsl[8] = 0, ...
- lpsl[9] = 3, lpsl[8] = lpsl[10] = 0, lpsl[7] = lpsl[11] = 1, ...
也就是说，lpsl数组可能存在以回文中心为轴的对称性，这并不难理解。以lpsl[6] = 6为例，左侧的lpsl[5] = 1，就说明以position 5为中心的短回文串是以postion 6为中心的长回文串的子串，那么在这个长回文串的右侧必然也存在同样的短回文串。所以，随着lpsl数组的值不断被计算出来，通过充分利用上述对称性，我们就有可能通过左侧已知的lpsl值直接求出右侧未知的lpsl值，而不必从头到尾都用中心扩展法。
算法操作
Manacher算法的初始操作其实就是中心扩展法，但是之后的思路会更聪明一些。具体该如何操作呢？下面就来研究算法运行了一段时间之后的一般情况，如图所示。
初看可能会感到一头雾水，先解释一下几个符号的含义。
- 当前已经遍历到的点记为i。也就是说，在i左侧的点的lpsl值都是已知的；
- 在i左侧有一个回文串中心点C，以C为中心的回文串右边界为R，左边界为R'，并且该回文串的R在当前是最大的，也就是右边界是最靠右的；
- i点关于C的对称点记为i'，显然lpsl[i']已经算出来了，并且有i' - R' = R - i。
那么，我们如何判断能否利用lpsl[i] = lpsl[i']的特性来减少计算量呢？下面将以i'为中心的回文串称为当前回文串，以C为中心的回文串称为最右回文串，分3种情况来讨论。
当lpsl[i'] < i' - R'，即lpsl[i'] < R - i时，说明当前回文串就是最右回文串的子串，所以直接满足最右回文串中R'-C-R的对称性，赋值lpsl[i] = lpsl[i']即可。
当lpsl[i'] = i' - R' = R - i时，说明当前回文串的左边界与最右回文串的左边界重合了，此时仍然满足lpsl[i] = lpsl[i']。但是，R'有可能同时也是原始字符串的左边界，亦即右边的lpsl[i]是有可能更大的，所以接下来应该继续用中心扩展法求出最终的lpsl[i]。
当lpsl[i'] > i' - R'，即lpsl[i'] > R - i时，说明当前回文串的左边界超出了最右回文串的左边界，此时以i点为中心的回文串右边界应该与最右回文串右边界重合，即lpsl[i] = R - i。很显然，如果lpsl[i] > R - i的话，就违反了前述最右回文串的定义，亦即存在一个R更靠右的回文串，产生了矛盾。
以上三种情况都是在i < R的前提下讨论的。如果i >= R，就没有必要利用最右回文串的性质了，直接用中心扩展法从i开始扩展就行了。
最后，我们何时需要更新C和R的位置呢？
容易得知，当以i为中心的回文串右边界超过了R时，现在的C就失效了，需要将C更新到i的位置，并且将R更新到以i为中心的回文串右边界。
代码实现
水到渠成。
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
String t = fill(s);
int n = t.length();
int[] lpsl = new int[n];
int c = 0, r = 0;
for (int i = 1; i < n - 1; i++) {
int im = 2 * c - i; // i'
lpsl[i] = i < r ? Math.min(lpsl[im], r - i) : 0; // 三种情况综合起来就是取lpsl[i']和r - i的较小值而已
while (t.charAt(i - lpsl[i] - 1) == t.charAt(i + lpsl[i] + 1)) {
lpsl[i]++; // 中心扩展法更新lpsl
}
if (i + lpsl[i] > r) { // 更新C和R
c = i;
r = i + lpsl[i];
}
}
int ml = -1, mc = -1;
for (int i = 1; i < n - 1; i++) {
if (lpsl[i] > ml) { // 找到lpsl最大的点
mc = i;
ml = lpsl[i];
}
}
int ms = (mc - ml) / 2; // 除2即可映射到原串的下标
return s.substring(ms, ms + ml);
}
private String fill(String s) {
String t = "|";
for (int i = 0; i < s.length(); i++) {
t += s.charAt(i) + "|";
}
return t;
}
}
复杂度分析
空间复杂度显然为O(n)，但是从代码看是for循环套一个while循环，为什么时间复杂度也是O(n)呢？思考：
- 当i < r时，不会进while循环，lpsl[i]的值可以O(1)地得出。
- 当i > r时，会进入while循环，但是根据上述最右回文串的定义，r肯定是单调递增的，不可能向前退。又因为i会从r + 1开始扫描，故直到整个算法结束，字符串中的每个字符最多只会被访问2次。
正因为进入while循环是有严格的条件的，所以实际的时间复杂度是线性的。
The End
本文配图来自geeksforgeeks.org上的相关系列文章。
凌晨有球看（争冠关键战哈哈），民那晚安晚安。
网友评论