算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

   求一个字符串的最长回文串。串长度小于110,000。

吐槽:

    1. O(nlogn)构造后缀数组超时... O(n)的不会... 是我写挫了 ????
    2. 拖了一年多才重新捉这题... 该打......

算法分析:

    直接上Manacher算法,详解在这里
    为什么P[i] = min(P[id - (i - id)], (P[id] + id) - i) 呢? 自己画一画就知道了......

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cassert>
 5 #include<cstring>
 6 using namespace std;
 7 #define re(i,n) for(int i = 0;i<n;i++)
 8 const int N = 250000;
 9 template <typename T> inline void chkmax(T &a,const T b) {if(a<b) a = b;}
10 int num[N],P[N];
11 char ch[N];
12 int main(){
13     while(~scanf("%s",ch)){
14         int n = strlen(ch);
15         int N = 1;
16         num[0] = 300;
17         re(i,n) {
18             num[N++]=99;
19             num[N++]=ch[i]-'a'; 
20         }
21         num[N++]=99;
22         num[N++]=100;
23         int id =0 ,mx = 1,ans = 0;
24         for(int i=1;i<N;i++){
25             if(mx > i) {
26                 P[i] = min(P[2*id - i], mx - i);
27             }
28             else P[i] = 1;
29             for(;num[i+P[i]]==num[i-P[i]];P[i]++);
30             if(i+P[i]-1 >= mx){
31                 mx = i + P[i]-1;
32                 id = i;
33             }
34             chkmax(ans,P[i]-1);
35         }
36         cout<<ans<<endl;
37     }
38 }
39 
posted on 2012-05-02 21:26 西月弦 阅读(513) 评论(0)  编辑 收藏 引用 所属分类: 解题报告经典题目

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理