poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

本文主要是介绍poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求一段字符串中的最长回文串。

因为数据量比较大，用原来的O（n^2）会爆。

小白上的O(n^2)解法代码：TLE啦~

#include<stdio.h>
#include<string.h>
const int Maxn = 1000000;char s[Maxn];int main()
{char e[] = {"END"};while(scanf("%s", s) != EOF){getchar();if(strcmp(e, s) == 0)break;int ncase = 1;int ans = 0;int len = strlen(s);for(int i = 0; i < len; i++){//奇数时for(int j = 0; i - j >= 0 && i + j < len; j++){if(s[i - j] != s[i + j])break;if(j * 2 + 1 > ans)ans = j * 2 + 1;}//偶数时for(int j = 0; i - j >= 0 && i + j + 1 <len; j++){if(s[i - j] != s[i + j + 1])break;if(j * 2 + 2 > ans)ans = j * 2 + 2;}}printf("Case %d: %d\n", ncase, ans);ncase++;}return 0;
}

然后找了百度，百度说要用Manacher算法可以用O（n）直接解决问题。

poj 3974 代码：

#include<stdio.h>
#include<string.h>
const int MaxN = 1000001;
char oldstr[MaxN];
char newstr[MaxN << 1];
int p[MaxN << 1];int min(int a, int b)
{return a < b ? a : b;
}int Pre()
{char head = '$';char middle = '#';char end = '?';int n = 0;newstr[n ++] = head;newstr[n ++] = middle;for(int i = 0; oldstr[i]!='\0'; i ++){newstr[n ++] = oldstr[i];newstr[n ++] = middle;}newstr[n ++] = end;return n;
}int Manacher(int n)
{int MaxID = 0;int MaxL = 0;int id = 1;p[0] = 0;for(int i = 1; i < n; i ++){if(MaxID > i)p[i] = min(p[2 * id - i], MaxID - i);elsep[i] = 1;while(newstr[i - p[i]] == newstr[i + p[i]])p[i] ++;if(p[i] + i > MaxID){MaxID = p[i] + i;id = i;}if(p[i] > MaxL){MaxL = p[i];}}return MaxL - 1;
}int main()
{char e[] = {"END"};int ncase = 1;while(scanf("%s", oldstr)!=EOF){if(strcmp(e, oldstr) == 0)break;printf("Case %d: ", ncase);ncase ++;int len = Pre();int ans = Manacher(len);printf("%d\n", ans);}return 0;
}

hdu 3068 数据比poj上弱，所以也顺利ac：

#include<stdio.h>const int MaxN = 110001;
char oldstr[MaxN];
char newstr[MaxN << 1];
int p[MaxN << 1];int min(int a, int b)
{return a < b ? a : b;
}int Pre()
{char head = '$';char middle = '#';char end = '?';int n = 0;newstr[n ++] = head;newstr[n ++] = middle;for(int i = 0; oldstr[i]!='\0'; i ++){newstr[n ++] = oldstr[i];newstr[n ++] = middle;}newstr[n ++] = end;return n;
}int Manacher(int n)
{int MaxID = 0;int MaxL = 0;int id = 1;p[0] = 0;for(int i = 1; i < n; i ++){if(MaxID > i)p[i] = min(p[2 * id - i], MaxID - i);elsep[i] = 1;while(newstr[i - p[i]] == newstr[i + p[i]])p[i] ++;if(p[i] + i > MaxID){MaxID = p[i] + i;id = i;}if(p[i] > MaxL){MaxL = p[i];}}return MaxL - 1;
}int main()
{while(scanf("%s", oldstr)!=EOF){int len = Pre();int ans = Manacher(len);printf("%d\n", ans);}return 0;
}

附：

我觉得百度文库上的这篇文章讲这个算法讲的很好，理解了一个下午，终于理解了。

求回文子串 O(n) manacher 算法：

回文串定义：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
回文子串，顾名思义，即字符串中满足回文性质的子串。

经常有一些题目围绕回文子串进行讨论，比如HDOJ_3068_最长回文，求最长回文子串的长度。朴素算法是依次以每一个字符为中心向两侧进行扩展，显然这个复杂度是O(N^2)的，关于字符串的题目常用的算法有KMP、后缀数组、AC 自动机，这道题目利用扩展KMP可以解答，其时间复杂度也很快O(N*logN)。但是，今天笔者介绍一个专门针对回文子串的算法，其时间复杂度为O(n)，这就是manacher 算法。

大家都知道，求回文串时需要判断其奇偶性，也就是求aba 和abba 的算法略有差距。然而，这个算法做了一个简单的处理，很巧妙地把奇数长度回文串与偶数长度回文串统一考虑，也就是在每个相邻的字符之间插入一个分隔符，串的首尾也要加，当然这个分隔符不能在原串中出现，一般可以用‘#’或者‘$’等字符。

算法大致过程是这样。
先在每两个相邻字符中间插入一个分隔符，当然这个分隔符要在原串中没有出现过。
一般可以用’#’分隔。
这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑了。
然后用一个辅助数组P记录以每个字符为中心的最长回文串的信息。
P［i］记录的是以字符str［i］为中心的最长回文串。
当以str［i］为第一个字符，这个最长回文串向右延伸了P［i］个字符。

为了防止越界，我们要在最后一个边界增加一个特殊标记，我们记为’$’.
当然，开始位置我们也最好标记一下，我们记为’?’。

这样一来，原来的奇数长度回文串还是奇数长度，偶数长度的也变成以‘#’为中心的奇数回文串了。
接下来就是算法的中心思想，用一个辅助数组P 记录以每个字符为中心的最长回文半径，也就是P[i]记录以Str[i]字符为中心的最长回文串半径。P[i]最小为1，此时回文串为Str[i]
本身。
我们可以对上述例子写出其P 数组，如下

新串：     $   #   a   #   b   #   a   #   a   #   b   #   ?
P[] ：    0   1   2   1   4   1   2   5   2   1   2   1   0
i：       0   1   2   3   4   5   6   7   8   9  10  11  12

这样一来，原来的奇数长度回文串还是奇数长度，偶数长度的也变成以‘#’为中心的奇数回文串了。

接下来就是算法的中心思想，用一个辅助数组P 记录以每个字符为中心的最长回文半径，也就是P[i]记录以Str[i]字符为中心的最长回文串半径。

P[i]最小为1，此时回文串为Str[i]本身。

这里有一个性质：P[i]-1 就是以Str[i]为中心的回文串在原串当中的长度。证明：1.对于任一一个原始的str[i],p[i]都是偶数。看上面的abaab即可明白。2.由于以Str[i]为中心的最长回文串(不能使#)显然是奇数，我们设为L。

3.如果知道了L,则删除#后，剩下的就是原始字符串长度还是最长回文串，长度是(L – 1) / 2.

4.显然，L = p[i] * 2 -1;这样就证明了上面的性质。

5.所以，长度 = (p[i] * 2 -1 – 1) / 2 = P[i]-1。

核心代码：

int Manacher(int n)
{int MaxID = 0;int MaxL = 0;int id = 1;p[0] = 0;for(int i = 1; i < n; i ++){if(MaxID > i)p[i] = min(p[2 * id - i], MaxID - i);elsep[i] = 1;while(newstr[i - p[i]] == newstr[i + p[i]])p[i] ++;if(p[i] + i > MaxID){MaxID = p[i] + i;id = i;}if(p[i] > MaxL){MaxL = p[i];}}return MaxL - 1;
}

我们用MaxId 变量记录在求i 之前的回文串中，延伸至最右端的位置，同时用id 记录取这个MaxId 的id 值。
通过下面这句话，算法避免了很多没必要的重复匹配。

if(MaxID > i)p[i] = min(p[2 * id - i], MaxID - i);

解释：(理解的难点 自己模拟了好多次)

利用了回文串的对称性，如下图：

i = 2 * id - j 即为i 关于id 的对称点，根据对称性，P[j]的回文串也是可以对称到i 这边的,但是如果P[j]的回文串对称过来以后超过MaxId 的话，超出部分就不能对称过来了，如下
图，所以这里P[i]为的下限为两者中的较小者，p[ i ] = Min ( p[ 2 * id - i] , MaxId - i);

算法的有效比较次数为MaxId 次，所以说这个算法的时间复杂度为O(n)。

这篇关于poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---