HDU 3068 最长回文(manacher O(n)求回文算法)

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

最长回文

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5327 Accepted Submission(s): 1817

Problem Description

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaaabab

Sample Output

4
3

Source

2009 Multi-University Training Contest 16 - Host by NIT

Recommend

lcy

表示这个O（n）的算法很厉害，学习起来和写起来都比较简单，学习了，下面转一篇文章，说的很清楚！

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAX 120000
#define MIN(a,b) (a>b?b:a)
char str[MAX];
char rec[MAX*2];
int ans[MAX*2];
int main()
{int len,i,j,k;int M_pos,pos;int count;while(scanf("%s",str)!=EOF){j=0;count=1;M_pos=0;pos=0;rec[j++]='@';for(i=0;str[i];i++){rec[j++]='#';rec[j++]=str[i];}rec[j++]='#';rec[j]=0;for(i=1;i<j;i++){if(M_pos > i)ans[i]=MIN(ans[pos*2-i],M_pos-i);elseans[i]=1;for ( ;rec[i+ans[i]]==rec[i-ans[i]] ;ans[i]++) ;if(i+ans[i] > M_pos)pos=i,M_pos=i+ans[i];}for(i=1;i<j;i++)if(count < ans[i])count=ans[i];printf("%d\n",count-1);}return 0;
}

下面文章转自： http://acm.uestc.edu.cn/bbs/read.php?tid=3258

说的很清楚，明白，学习了！

O（n）回文子串算法

这里，我介绍一下O（n）回文串处理的一种方法。Manacher算法.
原文地址：
http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/
其实原文说得是比较清楚的，只是英文的，我这里写一份中文的吧。
首先：大家都知道什么叫回文串吧，这个算法要解决的就是一个字符串中最长的回文子串有多长。这个算法可以在O（n）的时间复杂度内既线性时间复杂度的情况下，求出以每个字符为中心的最长回文有多长，
这个算法有一个很巧妙的地方，它把奇数的回文串和偶数的回文串统一起来考虑了。这一点一直是在做回文串问题中时比较烦的地方。这个算法还有一个很好的地方就是充分利用了字符匹配的特殊性，避免了大量不必要的重复匹配。
算法大致过程是这样。先在每两个相邻字符中间插入一个分隔符，当然这个分隔符要在原串中没有出现过。一般可以用‘#’分隔。这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑了（见下面的一个例子，回文串长度全为奇数了），然后用一个辅助数组P记录以每个字符为中心的最长回文串的信息。P［id］记录的是以字符str［id］为中心的最长回文串，当以str［id］为第一个字符，这个最长回文串向右延伸了P［id］个字符。
原串： w aa bwsw f d
新串： # w # a # a # b # w # s # w # f # d #
辅助数组P： 1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1
这里有一个很好的性质，P［id］-1就是该回文子串在原串中的长度（包括‘#’）。如果这里不是特别清楚，可以自己拿出纸来画一画，自己体会体会。当然这里可能每个人写法不尽相同，不过我想大致思路应该是一样的吧。
好，我们继续。现在的关键问题就在于怎么在O（n）时间复杂度内求出P数组了。只要把这个P数组求出来，最长回文子串就可以直接扫一遍得出来了。
由于这个算法是线性从前往后扫的。那么当我们准备求P［i］的时候，i以前的P［j］我们是已经得到了的。我们用mx记在i之前的回文串中，延伸至最右端的位置。同时用id这个变量记下取得这个最优mx时的id值。（注：为了防止字符比较的时候越界，我在这个加了‘#’的字符串之前还加了另一个特殊字符‘$’，故我的新串下标是从1开始的）
好，到这里，我们可以先贴一份代码了。

复制代码