題目描述：
求一個字符串的最長回文串。串長度小于110,000。
吐槽：
1. O(nlogn)構造后綴數組超時... O(n)的不會... 是我寫挫了 ????
2. 拖了一年多才重新捉這題... 該打......
算法分析：
為什么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
西月弦 閱讀(525)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告 、
經典題目