51nod1079中国剩余定理

发表于 | 分类于 |

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<stdio.h>
#include<string.h>
#include<algorithm>
int p[200003];
char s[100001];
char str[200003];
using namespace std;
void pk(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++]='#';
    }
    //str[len]='\n';
    pk(l);
    for(i=0;i<l;i++)
        ans=max(ans,p[i]);
    printf("%d\n",ans);
}