Tag Archives: 回文

hihoCoder 1032-最长回文子串

2 Replies

hihoCoder 1032-最长回文子串 #1032 : 最长回文子串 时间限制:1000ms 单点时限:1000ms 内存限制:64MB 描述 小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。 这一天，他们遇到了一连串的字符串，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，你能不能分别在这些字符串中找到它们每一个的最长回文子串呢？” 小Ho奇怪的问道：“什么叫做最长回文子串呢？” 小Hi回答道：“一个字符串中连续的一段就是这个字符串的子串，而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串，所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~” 小Ho道：“原来如此！那么我该怎么得到这些字符串呢？我又应该怎么告诉你我所计算出的最长回文子串呢？ 小Hi笑着说道：“这个很容易啦，你只需要写一个程序，先从标准输入读取一个整数N（N<=30)，代表我给你的字符串的个数，然后接下来的就是我要给你的那N个字符串（字符串长度<=10^6)啦。而你要告诉我你的答案的话，只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了！你看这就是一个例子。” 提示一 提示二 提示三 提示四 样例输入 3 abababa aaaabaa acacdas 样例输出 7 5 3

这个题目有很多解法，具体可以看这里，其中的中心扩展法很有意思，不过时间复杂度$$O(n^2)$$。后来发现Manacher算法时间复杂度只要$$O(n)$$，膜拜之，无奈研究了很久也没理解，很多中文博客写得不够全面详细，直到我看了这篇文章，明白了。主要思路如下： 1. 首先将字符串S预处理成T。在S的字符之间插入#字符，如下：
For example: S = “abaaba”, T = “#a#b#a#a#b#a#”.
这样之后，不管S长度是奇数还是偶数，得到的T都是奇数，这样就不需要分情况讨论了，也方便了后面的求解。 2. 我们将中间结果存储在数组P中：
T = # a # b # a # a # b # a # P = 0 1 0 3 0 1 6 1 0 3 0 1 0
P[i]表示以T[i]为中心，T中回文串的半径，比如T[3]=b，P[3]=3，表示以b为中心，T中回文串的半径为3，也就是#a#b#a#，半径就是#a#，而P[3]=3也正好是原始串S中以b为中心的回文串的总长度，即回文串aba的长度为3. 所以我们只需要求出数组P，然后求P中的最大值即为S中最长回文串的长度。 3. 为了求数组P，有两种情况需要讨论。假设我们已经求出一部分数组P的值了，如下图所示： C为目前P中最大值的位置，C为目前T中使得R推进到最右边的回文串的中心位置center（不一定是P的最大值的位置，最大值还需要在最后一步求解），它的半径是9，所以左边（Left）到达L，右边（Right）到达R，下标分别是2和20. 4. 第一种情况是，如果此时i=13，则P[13]等于多少呢？ i的对称点i’下标为9，P[i’]=1，它的回文串没有超出以C为中心的回文串，根据对称性，则P[i]=P[i’]=1. 5. 第二种情况是，如果i=15，则P[15]等于多少呢？ 由图可知，i的对称点i’=7，P[i’]=7，即以i’为中心的回文串已经超出了以C为中心的回文串，L左边的红色线条即为超出部分。那么此时不能说P[i]=P[i’]=7，因为如果这样的话，那么以C为中心的回文串也可以扩展到红色线条部分，这样P[C]就大于原来的P[C]了。但是可以肯定的是，i的半径至少是R-i=5，所以我们可以在此基础上依次增加i的半径，判断是否还是回文串。 6. 总结一下就是：
if P[ i’ ] ≤ R – i, then P[ i ] ← P[ i’ ] else P[ i ] ≥ P[ i’ ]. (Which we have to expand past the right edge (R) to find P[ i ].
更详细的解释和部分代码实现请看原博文，下面是我的针对hihoCoder #1032 : 最长回文子串提交的代码： [cpp] #include&lt;iostream&gt; #include&lt;string&gt; using namespace std; //字符串预处理，插空#，首尾分别^&amp; string pre_process(string s) { string rs; int s_len=s.size(); if(s_len==0) return "^&amp;"; rs="^"; for(int i=0;i&lt;s_len;i++) //rs+="#"+s[i];//const char* 和int/char不能相加，指针越界 rs+="#"+s.substr(i,1);//const char*和string可以相加 return rs+"#&amp;"; } int get_longest_pal_len(string s) { string T=pre_process(s); int n=T.size(); int *P=new int[T.size()]; P[0]=0; int C=0,R=0; for(int i=1;i&lt;n-1;i++) { int i_mirror=2*C-i;//i的对称位置 P[i]=(R&gt;i)?min(R-i,P[i_mirror]):0;//如果R&gt;i，说明i还在R里面，如果P[i_mirror]&lt;=R-i，则类似图中i=13；如果P[i_mirror]&gt;R-i，则P[i]至少是R-i的，然后从R-i递增测试 while(T[i+1+P[i]]==T[i-1-P[i]]) P[i]++; if(i+P[i]&gt;R)//更新最大的中心点和右边界 { C=i; R=i+P[i]; } } int max_len=0; for(int i=1;i&lt;n-1;i++) { if(P[i]&gt;max_len)//寻找最大P[i]，P[i]既是T[i]的回文串半径（包含#），也是以S[i]为中心的最长回文串长度。 max_len=P[i]; } delete[] P; return max_len; } int main() { int n; string s; cin&gt;&gt;n; while(n–) { cin&gt;&gt;s; cout&lt;&lt;get_longest_pal_len(s)&lt;&lt;endl; } return 0; } [/cpp] 这段代码有一小部分需要注意一下，就是string pre_process(string s);字符串预处理函数中的rs+=”#”+s.substr(i,1);不要写成了rs+=”#”+s[i];，因为”#”会隐式转换成const char*类型，而s[i]是char/int类型，”#”+s[i]相当于指针增加一个int偏移量，会导致指针越界。所以要写成”#”+s.substr(i,1)，因为string.substr返回的是string类型，const char*和string是可以相加（连接）的。看来我还是基础不牢啊~ ]]>