1089 最长回文子串 V2（Manacher算法）
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。
Input
输入Str（Str的长度 <= 100000)
Output
输出最长回文子串的长度L。
Input示例
daabaac
Output示例
5
看到这道题才特意去看了下Manacher算法；
参考博客：http://blog.csdn.net/pi9nc/article/details/9251455
http://blog.sina.com.cn/s/blog_70811e1a01014esn.html
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
|
#include<string.h>
#include<algorithm>
int p[200003];
char s[100001];
char str[200003];
using namespace std;
void (int len){
int i;
int mx=0,id=0;
for(i=1;i<len;i++){
if(mx>i)
p[i]=min(p[2*id-i],mx-i);
else
p[i]=0;
while(str[i+p[i]+1]==str[i-p[i]-1])
p[i]++;
if(p[i]+i>mx){
id=i;
mx=p[i]+id;
}
}
}
int main(){
int len,ans=0,i,l=2;
scanf("%s",s);
len=strlen(s);
str[0]='$';
str[1]='#';
for(i=0;i<len;i++){
str[l++]=s[i];
str[l++]='#';
}
pk(l);
for(i=0;i<l;i++)
ans=max(ans,p[i]);
printf("%dn",ans);
}
|
近期评论