这题的期望最优解应该是manacher算法…又叫manacher最长回文子串。
这里给出Python解法 和 C++解法…
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
|
1 2 3 4 5 |
Input: "babad" Output: "bab" Note: "aba" is also a valid answer. |
Example:
|
1 2 3 |
Input: "cbbd" Output: "bb" |
给出一个子串…然后求出它的最长回文子串。
注意：
这里一定要注意：不能用动态规划的求一个串和它的逆串的最长公共子串。
反例如下：
abcdecba
abcedcba
得到最长公共子串长度为3…但是…最长回文子串长度是1…
PS.明白最长公共子串和最长公共子序列的区别。
详情可以看我的博客动态规划小解里面最长公共子序列部分 ：http://blog.tk-xiong.com/archives/972
manacher算法…说实话昨天才学，讲肯定讲不好了。
先明白几个基本概念：
1. 回文串的表示方法：
这里采用了pos+len的表示方法…pos指回文串的中心位置的下标，len指回文串的向一边拓展的长度。
举个板栗子： 1 1 2 3 2 1 4 的最长回文子串是 1 2 3 2 1 对吧，它在原串中的下标是pos = 3 ，向其中一边拓展的长度是 len = 3 (这里3的计算是： 1 2 3 或者 3 2 1 ,即上面标红的部分的长度。)
暂不纠结为什么这么算，等会自然明白了。
2. manacher算法需要预处理：
1 2 3 2 1 表示回文串，找中心很好找，但是 1 2 3 3 2 1 的pos是多少？请问了…
这个我反正不知道，所以manacher采用了预处理的方式来解决这种奇数长子串与偶数长子串难以处理的问题…
方式就是加上…特殊字符。是什么字符无所谓，但是一定要是原串中没有出现过的字符。
比如原串中只有字母数字，那我可以加个特殊字符’#’.(后面就以#来举例)
然后我们再看看上面的串。经过处理后如下：
原串： 1 1 2 3 2 1 4
处理过后的串： # 1 # 1 # 2 # 3 # 2 # 1 # 4 #
额，不考虑空格，空格只是为了方便看而已。
然后接下来我们可以看到。无论你原来的串是奇数还是偶数，都统统变成了奇数。对不对？
举个例子: 1 2 3 2 1 的串变成了 # 1 # 2 # 3 # 2 # 1 # (长度为11)
原本是 1 2 3 3 2 1 的串变成了 # 1 # 2 # 3 # 3 # 2 # 1 # (长度为13)
3. 预处理后的串的单向长度和下标与原串的总长度与下标关系：
这个是为了方面最后获得处理前的最长回文子串。
这个’单向长度’是个人杜撰的一个词…实在是不知道怎么叫比较好。
不过举个例子①： 1 2 3 2 1 的长度是 5
它的预处理后的串 # 1 # 2 # 3 # 2 # 1 # 的单向长度是 6
换个例子②： 1 2 3 3 2 1 的长度是 6
它做了预处理之后的串是 # 1 # 2 # 3 # 3 # 2 # 1 # ,单向长度是 7
看懂了吧？看不懂？自己再思考思考，请注意这里是处理后的串的单向长度与原串的总长度的关系。
下标的话，以上例：
①：pos = 2 , maxPos = 5
②：pos = 3, maxPos = 6
这里假设偶数一定要取pos的话，则取中间两个的后一个的下标，比如这里的两个3，则取后面一个3的下标。
故得到计算方式：
pos = maxPos / 2;
len = maxLen – 1;
4. 得到原串的长度和下标后，计算[begin, end)的值：
还是以上面的例子①②为例：
①：1 2 3 2 1
②：1 2 3 3 2 1
首先看①：
begin = pos – len/2 = 2 – 5/2 = 0;
end = pos + (len+1)/2 = 2 + (5+1)/2 = 5
正好符合了前闭后开的要求 [0, 5)
然后看②：
begin = pos – len/2 = 3 – 6/2 = 0
end = pos + (len+1)/2 = 3 + 7/2 = 3 + 3 = 6
也正好符合前闭后开的要求：[0, 6)
PS.关于不是整个串都是回文的情况，可自己代入计算验证。
PS.关于奇数和偶数的begin和end的计算，也可以自己思考，为何end的计算要+1…
好，接下来，我们就开始讲manacher算法了。
这里我们主要的工作是 对预处理之后的串计算一个RL数组(计算对应每一个pos的回文的单向长度值)。
为啥叫RL，是因为是计算的是从pos开始向右的长度，RightLen…比如 1 2 3 3 2 1.懂了吧？
举个例子，在只有 a 这一个字符的情况下，pos = 0,RL[0] = 1
这里：RL[0] = 1 表示以pos=0为中心的回文的单向长度是1
但是实际上，我们会对a进行预处理…
所以实际上得到的串是： # a #
维护的RL数组是：[1, 2, 1]
这里RL[0] = 1, RL[1] = 2, RL[2] = 1.
请记住，RL是单向长度…
然后我们可以得到最长的单向长度是RL[1],则返回:
maxPos = 1, maxLen = RL[maxPos] = 2;
当然，如果你翻看上面的内容，可以看到如何转化为原串的长度信息：
pos = maxPos / 2 = 0
len = maxLen – 1 = 1
得到，原串中的最长回文子串的中心下标是0，长度是1.
经过计算得到begin和end的值为： [0, 1)
然后就可以得到原串了，懂了吧？
刚才我们讲了RL数组是什么，相信大家都理解了。
现在我们来讲怎么计算RL数组。
举个例子：
对于串 ： abcbabcba 这个串。
处理后：#a#b#c#b#a#b#c#b#a# 这样的。
接下来我们对数组的每一项计算RL。
现在我们先不采用manacher算法的优化，先只讲怎么计算RL…
计算方法是从pos开始，分别往左右拓展，判断是否相等，如果相等，说明单向长度可以增加1对不对？然后再拓展一次，再增加一次。
代码主要如下： 下标用i表示…
while i-RL[i] >= 0 and i+RL[i] < len(s) and s[i-RL[i]] == s[i+RL[i]] :
RL[i] += 1
这里相信大家看得懂…
在对pos = i的元素拓展长度为RL[i]时，不越界(粉色代码)
并且左右两边的值相等，(红色代码)，则继续拓展。
这个相信大家一看就懂了。
这就是RL的基本计算方法。那么manacher是怎么讲代码优化到O(n)的呢…
相信大家看这么久也烦了，莫烦，这么精妙的代码值得我们花很多时间去学…
如果觉得就想赶紧解决的话，请跳到最后，有kuangbin大神的模板…
接下来我们讲优化技术…如何通过之前已经计算过的RL值来优化当前的计算次数。
我这里会很慢，先带大家一项一项计算…
以#a#b#c#b#a#b#c#b#a#为例。
先将数组初始化为1…因为我们可以确定，每一项的单向长度肯定是大于等于1的对不对？
于是得到数组 RL[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] (共19项)
先计算第0项：
发现 0 – RL[0] 越界了，于是跳下一项…
第1项：
再看看代码：
while i-RL[i] >= 0 and i+RL[i] < len(s) and s[i-RL[i]] == s[i+RL[i]] :
RL[i] += 1
发现 s[i-RL[i]] == s[i+RL[i]] (两边都是#)
于是增加1，再拓展一次，越界了，得到RL的值为2，对吧？
RL[1,2,1,…]
然后接下来，第2项(别忘了是下标为2)：
#两边分别为a和b，不相等，不拓展对不对？
第3项：
b两边为#，可以拓展，然后再两边为a和c（a#b#c），不能拓展了，得到值2：
RL[1,2,1,2,1…]
第4项(记得这个数字是下标啊！！！)：
#两边是b和c不能拓展对不对。
第5项：
我先拷贝下来，免得读者您上下乱找：
#a#b#c#b#a#b#c#b#a#
第五项是我标红的c，这里左右分别是#,b,#,a,#，然后越界了。
所以最终拓展了5次，得到单向长度RL的值为6…对不对？
然后我再复制一次…给您看一个发现可以避免重复计算的东西：
#a#b#c#b#a#b#c#b#a#
中间的c我加粗了，你看它左右两边，是不是有一样的内容，#b#?
那我还要这么麻烦的算后面的项吗？不用了呀，我直接把左右的拷贝过去行不行呢？
可以的！但是拷贝完了之后还要继续拓展！
不信？我们来算一算。
我先算完第8项(注意是下标我的哥…)。都是没错的，对不对。
得到 RL[1,2,1,2,1,6,1,2,1,…]
然后我算第9项…(这里的1是还没改变的值)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| # | a | # | b | # | c | # | b | # | a | # | b | # | c | # | b | # | a | # |
| 1 | 2 | 1 | 2 | 1 | 6 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
我当然会把关于c（粉色）对称的的那个a(下标为1,红色)的值直接拷贝过来呀…
得到RL[9] = 2, 然后发现，是不是不太对？好像还可以拓展呀！
于是我继续执行拓展代码：
while i-RL[i] >= 0 and i+RL[i] < len(s) and s[i-RL[i]] == s[i+RL[i]] :
RL[i] += 1
发现最终值可以拓展到10对不对？好像把整个范围都包住了。之前的c并没有包住整个串对不对？
于是修改RL[9] = 10…
再回过头来一看，我这样好像相对之前少计算了几次，是不是？
这就是manacher省下的时间…现在我们重新来学习manacher算法…
沃德天？看了这么久，才真正开始？
是的…我之前只是在告诉你一些基本的概念，如果这些东西你不理解的话，这个算法你学不好，如果你一上来就看那些乱七八糟的理论，图例，只会把你的脑袋冲的昏昏的…
现在。我们来看看manacher的优化之处：
前面我们是不是提到了，回文的两端具有相似性，比如前面的c的两边的b的值就是一样的。
所以我们在此维护一个MaxRight值，和MaxRightPos值…用来表示，我当前找到过的回文串向右覆盖的最右的位置和这个向右覆盖的最右的回文串的下标…
用来干嘛呢？当然是优化计算啊！
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| # | a | # | b | # | c | # | b | # | a | # | b | # | c | # | b | # | a | # |
| 1 | 2 | 1 | 2 | 1 | 6 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
还是以这里刚刚计算9的时候距离…
请重新计算，并维护一个MaxRight和MaxRightPos的值，然后如果我们当前计算的下标在我之前计算的回文的计算过的范围内的话(即 i < MaxRight)，则可以先用之前计算过的关于MaxRightPos对称的位置RL[2*MaxRightPos-i] 来替代RL[i]，然后再进行拓展计算。
比如： 这里关于下标为5的对称。 4和6, 3和7，2和8。
至于1和9，它们小范围内(#a#)是不是对称的？
不论证算法为啥这样就优化到O(n)了。
要注意一点，如果MaxRight – i ，即它到边界的距离比对称位置的RL值小的话，说明它的值不能直接用对称位置来替代。举个例子：
#b#a#b#c#b#a#
这里我们计算c之后，得到最优覆盖位置到了最右边，但是左边的a的RL[3] = 4(单向长)，右边的却只有2..
懂了吧，所以要注意下边界情况。
下面我应该可以直接上代码了…
PS.记得每计算一次回文，就更新一下覆盖到最右的那个回文的最右值和对应的下标呀。
Python代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
class Solution(object): def manacher(self, s): #初始化串 s = '#' + '#'.join(s) + '#' RL = [1] * len(s) #初始化为1的RL数组 MaxRight = 0 #向右覆盖的回文的最右边的下标 MaxRightPos = 0 #上面那个回文子串的中间下标 MaxLen = 0 #这是单向最长长度 MaxPos = 0 #这是上面那个子串的中间下标 for i in range(len(s)) : #如果在向右覆盖最长回文串的范围内，则获得之前算过的数据，不在范围内，则默认为1 if i < MaxRight : RL[i] = min(RL[2*MaxRightPos-i], MaxRight - i) #然后尝试做最长的拓展，注意边界判断 while i-RL[i] >= 0 and i+RL[i] < len(s) and s[i-RL[i]] == s[i+RL[i]] : RL[i] += 1 #更新MaxRight，MaxRightPos if i + RL[i] - 1 > MaxRight : MaxRight = RL[i] + i - 1 MaxRightPos = i #更新最长长度 if RL[i] >= MaxLen : MaxLen = RL[i] MaxPos = i #经过计算，返回原串最长长度和下标 return (MaxLen-1, MaxPos/2) def longestPalindrome(self, s): """ :type s: str :rtype: str """ MaxLen,pos = self.manacher(s); return s[pos-(MaxLen/2) : pos+((MaxLen+1)/2)] |
C++代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
class Solution { public: string manacher(string s) { //1.预处理： string str = "#"; for(int i = 0; i < s.length(); i++) { str += s.substr(i, 1); str += "#"; } //2.初始化有一个vector数组...长度为s的长度...值为1 vector<int> RL(str.length(), 1); //3.定义最右覆盖数据 和 最大回文长度 int MaxRight = 0; //向右覆盖的回文的最右边的下标 int MaxRightPos = 0; //上面那个回文子串的中间下标 int MaxLen = 0; //这是单向最长长度 int MaxPos = 0; //这是上面那个子串的中间下标 //4.对每一个字符，以其下标为中心，计算RL值... for(int i = 0; i < str.length(); i++) { //如果i在已计算的回文覆盖范围内，则可用对称下标的值来初始化 //但是要注意，如果对称下标的范围超出了当前的MaxRight覆盖的范围，则只能取较小的。 if(i < MaxRight) { RL[i] = min(RL[MaxRightPos*2 - i], MaxRight - i); } //以i为中心，RL[i]为长度每次向左右拓展一个长度，直到无法拓展。 while((i-RL[i] >= 0) && (i+RL[i] < str.length()) && (str[i+RL[i]] == str[i-RL[i]])) { RL[i] += 1; } //更新MaxRight - 减一是因为RL[i]的值包括了i本身占了1 if(i+RL[i]-1 > MaxRight) { MaxRight = i+RL[i]-1; MaxRightPos = i; } //更新最长回文子串 if(RL[i] > MaxLen) { MaxLen = RL[i]; MaxPos = i; } } //5. 根据得到的MaxLen和MaxPos计算原串的值。 int pos = MaxPos / 2; int len = MaxLen - 1; //然后计算[begin, end)的值 - C++方法可以不算end的值 int begin = pos - len/2; //int end = pos + (len+1)/2; //6. 最后得到要返回的子串的内容 //string substr(int pos = 0,int n = npos) const;//返回pos开始的n个字符组成的字符串 string rt = s.substr(begin, len); return rt; } string longestPalindrome(string s) { return manacher(s); } }; |
大致是这样，有问题就可以留言。