hdu3068馬拉車

其實馬拉車還真是最好理解的算法（感覺初中的時候好像講過類似的，但是當時就沒有認真聽）

沒想到一個簡單的優化能變成O(n)，感覺碉堡

不說了，馬拉車裸題，我在寫的時候只保留了id，沒保留mx，希望能形成一種代碼習慣吧

 1 #include <cstdio>
 2 int n;char ch;
 3 int p[220002];
 4 char a[220002];
 5 int min(int a,int b){return(a<b)?a:b;}
 6 int max(int a,int b){return(a>b)?a:b;}
 7 int get(int k){return (k&1)?p[k]/2*2:(p[k]+1)/2*2-1;}
 8 void add(int i)
 9 {
10     int u=i-p[i],v=i+p[i];
11     while((a[u]==a[v]) && (u>0) && (v<=n))
12         u--,v++,p[i]++;    
13 }
14 int main()
15 {
16     while((ch<'a' || ch>'z')&&(ch!=EOF)) ch=getchar();
17     while(ch!=EOF)
18     {
19         n=1;a[1]='0';
20         for(;ch>='a' && ch<='z';ch=getchar())
21             a[++n]=ch,a[++n]='0';
22         int id=0;
23         for(int i=1;i<=n;i++)
24         {
25             if(i<id+p[id])
26             {
27                 p[i]=min(p[id*2-i],id+p[id]-i);
28                 if(i+p[i]==id+p[id])
29                     add(i);
30             }
31             else
32                 p[i]=1,add(i);
33             if(i+p[i]>p[id]+id)
34                 id=i;
35         }
36         int ans=0;
37         for(int i=1;i<=n;i++)
38             ans=max(ans,get(i));
39         printf("%d\n",ans);
40         while((ch<'a' || ch>'z')&&(ch!=EOF)) ch=getchar();
41     }
42     return 0;
43 }

轉載于:https://www.cnblogs.com/wanglichao/p/5798856.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/256533.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/256533.shtml
英文地址，請注明出處：http://en.pswp.cn/news/256533.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！