|
It's great to be great, but it's greater to be human. 成为一个伟人很伟大，但是成为一个充满人性的人更伟大。 Manacher算法 Manacher于1975年发现了一种线性时间算法，可以在列出给定字符串中从任意位置开始的所有回文子串。同样的算法也可以在任意位置查找全部极大回文子串，并且时间复杂度是线性的。 之前在讲《517，最长回文子串的3种解决方式》的时候，在最后提到过Manacher算法，但是没有写，这里单独拿出来写。 我们先看一下回文串，回文串有两种形式，一种是奇数的比如"aba"，一种是偶数的比如"abba"。这里使用Manacher算法的时候，会在每个字符之间都会插入一个特殊字符，并且两边也会插入，这个特殊字符要保证不能是原字符串中的字符，这样无论原来字符串长度是奇数还是偶数，添加之后长度都会变成奇数。例如 "aba"-->"#a#b#a#"（长度是7） "abba"-->"#a#b#b#a#"（长度是9） 这里再来引用一个变量叫回文半径，通过添加特殊字符，原来字符串长度无论是奇数还是偶数最终都会变为奇数，因为特殊字符的引用，改变之后的字符串的所有回文子串长度一定都是奇数。并且回文子串的第一个和最后一个字符一定是你添加的那个特殊字符。其实很好证明 如果原来回文子串的长度是奇数，通过中间插入特殊字符，特殊字符的个数必定是偶数，在加上两边的特殊字符，长度必然是奇数 如果原来回文子串的长度是偶数，通过中间插入特殊字符，特殊字符的个数必定是奇数，在加上两边的特殊字符，长度必然是奇数 因为添加特殊字符之后所有回文子串的长度都是奇数，我们定义回文子串最中间的那个字符到回文子串最左边的长度叫回文半径，如下图所示。  我们来看个例子，比如字符串"babad"在添加特殊字符之后每个字符的回文半径  搞懂了这个我们再来看一下最长回文子串该怎么求。在第517题的时候我们讲过中心扩散法，我们会以每一个字符（中间会过滤掉重复的）为中心往两边扩散，如果以当前字符为中心往两边扩散计算完的时候，到下一个字符在往两边扩散的时候还要重新计算，那么有没有一种方法不用重新计算，而利用之前计算的结果呢，答案是肯定的。 假如以当前字符s[maxCenter]为回文中心的最大回文长度是从left到maxRight，如下图所示 如果我们想求以字符s[i]为回文中心的最大回文长度，我们只需要找到i关于maxCenter的对称点j，看下j的回文长度，因为j已经计算过了。 1，如果i在maxRight的左边，并且j的最大回文长度左边没有到达left，根据对称性，i的最大回文长度就等于j的最大回文长度，如下图所示  2，如果i在maxRight的左边，并且j的最大回文长度左边到达或者超过left，根据对称性，i的最小回文长度等于j-left也等于maxRight-i，至于最大能有多大，还需要在继续判断，如下图所示  3，如果i在maxRight的右边，我们就没法利用之前计算的结果了，这个时候就需要一个个判断了，如下图所示  如果还看不明白，我们来随便找个字符串"babcbabcbac"画个图来看下   代码如下，分三种情况判断 1 for (int i = 0; i < length; i++) { 2 if (i < maxRight) { 3 //情况一，i没有超出范围[left,maxRight] 4 //2 * maxCenter - i其实就是j的位置，实际上是判断p[j]<maxright - i< p=""> 5 if (p[2 * maxCenter - i] < maxRight - i) { 6 //j的回文半径没有超出范围[left,maxRight]，直接让p[i]=p[j]即可 7 p[i] = p[2 * maxCenter - i]; 8 } else { 9 //情况二，j的回文半径已经超出了范围[left,maxRight]，我们可以确定p[i]的最小值 10 //是maxRight - i，至于到底有多大，后面还需要在计算 11 p[i] = maxRight - i; 12 //继续计算 13 while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]]) 14 p[i]++; 15 } 16 } else { 17 //情况三，i超出了范围[left,maxRight]，就没法利用之前的已知数据，而是要一个个判断了 18 p[i] = 1; 19 //继续计算 20 while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]]) 21 p[i]++; 22 } 23 } 在来看下最终代码 1public String longestPalindrome(String s) { 2 int charLen = s.length();//源字符串的长度 3 int length = charLen * 2 + 1;//添加特殊字符之后的长度 4 char[] chars = s.toCharArray();//源字符串的字符数组 5 char[] res = new char[length];//添加特殊字符的字符数组 6 int index = 0; 7 //添加特殊字符 8 for (int i = 0; i < res.length; i++) { 9 res[i] = (i % 2) == 0 ? '#' : chars[index++]; 10 } 11 12 //新建p数组 ，p[i]表示以res[i]为中心的回文串半径 13 int[] p = new int[length]; 14 //maxRight(某个回文串延伸到的最右边下标) 15 //maxCenter(maxRight所属回文串中心下标), 16 //resCenter（记录遍历过的最大回文串中心下标） 17 //resLen（记录遍历过的最大回文半径） 18 int maxRight = 0, maxCenter = 0, resCenter = 0, resLen = 0; 19 //遍历字符数组res 20 for (int i = 0; i < length; i++) { 21 if (i < maxRight) { 22 //情况一，i没有超出范围[left,maxRight] 23 //2 * maxCenter - i其实就是j的位置，实际上是判断p[j]<maxright - i< p=""> 24 if (p[2 * maxCenter - i] < maxRight - i) { 25 //j的回文半径没有超出范围[left,maxRight]，直接让p[i]=p[j]即可 26 p[i] = p[2 * maxCenter - i]; 27 } else { 28 //情况二，j的回文半径已经超出了范围[left,maxRight]，我们可以确定p[i]的最小值 29 //是maxRight - i，至于到底有多大，后面还需要在计算 30 p[i] = maxRight - i; 31 while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]]) 32 p[i]++; 33 } 34 } else { 35 //情况三，i超出了范围[left,maxRight]，就没法利用之前的已知数据，而是要一个个判断了 36 p[i] = 1; 37 while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]]) 38 p[i]++; 39 } 40 //匹配完之后，如果右边界i + p[i]超过maxRight，那么就更新maxRight和maxCenter 41 if (i + p[i] > maxRight) { 42 maxRight = i + p[i]; 43 maxCenter = i; 44 } 45 //记录最长回文串的半径和中心位置 46 if (p[i] > resLen) { 47 resLen = p[i]; 48 resCenter = i; 49 } 50 } 51 //计算最长回文串的长度和开始的位置 52 resLen = resLen - 1; 53 int start = (resCenter - resLen) >> 1; 54 //截取最长回文子串 55 return s.substring(start, start + resLen); 56} 上面都通过画图分析很好理解，可能稍微有点不好理解的是后面3行代码，resLen就是最大回文半径，resCenter就是最大回文子串（添加特殊字符之后的）中间的那个字符。我们可以根据下面这个图可以看到，原字符串中回文串的长度就是添加特殊字符之后的回文半径-1。 上面是分为3种情况来判断的，实际上我们还可以把上面3种情况合并 1 //合并后的代码 2 p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * maxCenter - i]) : 1; 3 //上面的语句只能确定i~maxRight的回文情况，至于maxRight之后的部分是否对称， 4 //就只能一个个去匹配了，匹配的时候首先数组不能越界 5 while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]]) 6 p[i]++; 我们来看下合并后的最终代码 1// 返回最长回文串长度 2public String longestPalindrome(String s) { 3 int charLen = s.length();//源字符串的长度 4 int length = charLen * 2 + 1;//添加特殊字符之后的长度 5 char[] chars = s.toCharArray();//源字符串的字符数组 6 char[] res = new char[length];//添加特殊字符的字符数组 7 int index = 0; 8 //添加特殊字符 9 for (int i = 0; i < res.length; i++) { 10 res[i] = (i % 2) == 0 ? '#' : chars[index++]; 11 } 12 13 //新建p数组 ，p[i]表示以res[i]为中心的回文串半径 14 int[] p = new int[length]; 15 //maxRight(某个回文串延伸到的最右边下标) 16 //maxCenter(maxRight所属回文串中心下标), 17 //resCenter（记录遍历过的最大回文串中心下标） 18 //resLen（记录遍历过的最大回文半径） 19 int maxRight = 0, maxCenter = 0, resCenter = 0, resLen = 0; 20 //遍历字符数组res 21 for (int i = 0; i < length; i++) { 22 //合并后的代码 23 p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * maxCenter - i]) : 1; 24 //上面的语句只能确定i~maxRight的回文情况，至于maxRight之后的部分是否对称， 25 //就只能一个个去匹配了，匹配的时候首先数组不能越界 26 while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]]) 27 p[i]++; 28 //匹配完之后，如果右边界i + p[i]超过maxRight，那么就更新maxRight和maxCenter 29 if (i + p[i] > maxRight) { 30 maxRight = i + p[i]; 31 maxCenter = i; 32 } 33 //记录最长回文串的半径和中心位置 34 if (p[i] > resLen) { 35 resLen = p[i]; 36 resCenter = i; 37 } 38 } 39 //计算最长回文串的长度和开始的位置 40 resLen = resLen - 1; 41 int start = (resCenter - resLen) >> 1; 42 //截取最长回文子串 43 return s.substring(start, start + resLen); 44} 总结 Manacher算法，很多人习惯称它为马拉车算法，是一道非常经典的算法，搞懂他的原理，其实他的解题思路并不难。 |
|
|
