[原创]HDU 3068 最长回文 [Manacher]【字符串】

2017-01-08 23:01:19 Tabris_ 阅读数：237

博客爬取于2020-06-14 22:42:23
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54237933

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3068

---------------------------------------------------------.
最长回文

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

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
aaaa

abab

Sample Output
4
3

-------------------------------------------------------.

解题思路:
就是Manacher入门题目
Manacher 是一个能在O(n)O(n)的复杂度内解决字符串中最长回文子串的问题

这篇帖子给的挺详细的

附本题代码

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
74
75
76
77
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 500000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
/*************************************************/

/***
str  原字符串
a    进行Manacher算法的为减轻编码难度改进的字符串
p[i] 以a[i]为中心的回文串的半径(含a[i])
id   最长回文子串的中心位置
mx   id+p[id] 最长回文子串的左外边界。

算法核心的部分
if(mx > i) p[i] = (p[(id<<1)-i]<(mx-i))?p[(id<<1)-1]:(mx-i);
else p[i]=1;

首先我们知道对于一个字符串进行操作的时候，是从左到右依次进行的
那么由于回文串的对称性，
那么可以确定的是对于a[i]为中心的回文串的长度至少是在以这个最大的回文串中对称的那个位置为中心的回文串的长度,但只能确定的是在最大的回文串的那一部分中的长度,至于之外的就要一个个的匹配了

*/
/***
id  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7
a： $ # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
p_i 1 1 2 1 2 5 2

*/
char a[N],str[N];
int p[N];

void train(){
    int len  = 0;
    a[len] = '$', a[++len] = '#';
    int slen = strlen(str)-1;
    Rep(i,0,slen) a[++len] = str[i],a[++len] = '#';

    memset(p,0,sizeof(p));
    int id = -1,mx = -1,mxp = -1;
    Rep(i,0,len){
        if(mx > i) p[i] = (p[(id<<1)-i]<(mx-i))?p[(id<<1)-i]:(mx-i);
        else p[i]=1;
        while(a[i-p[i]]==a[i+p[i]]) p[i]++;
        if(p[i]+i>mx) mx=p[i]+i,id=i;
        if(p[i]>mxp) mxp = p[i];
    }
    printf("%d\n",mxp-1);
    return ;
}

int main(){
    while(~scanf("%s",str)) train();
    return 0;
}