<題目鏈接>

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?最長回文

Problem Description 給出一個只由小寫英文字符a,b,c...y,z組成的字符串S,求S中最長回文串的長度.
回文就是正反讀都是一樣的字符串,如aba, abba等 Input 輸入有多組case,不超過120組,每組輸入為一行小寫英文字符a,b,c...y,z組成的字符串S
兩組case之間由空行隔開(該空行不用處理)
字符串長度len <= 110000 Output 每一行一個整數x,對應一組case,表示該組case的字符串中所包含的最長回文長度. Sample Input aaaa abab Sample Output 4 3 #include <bits/stdc++.h> using namespace std;const int N = 2e5+5; int len[N]; char str[N],s[N];void init(){ //得到處理后的新字符串str[0]='@';int i;for(i=0;s[i]!=0;i++){str[2*i+1]='#';str[2*i+2]=s[i];}str[2*i+1]='#';str[2*i+2]=0; } int manacher(){int id=0,mx=0; //id為能當前能夠到達字符串最右端的回文串的中心位置for(int i=1;str[i];i++){len[i]=mx>i?min(len[2*id-i],mx-i):1; // 2*id-i，指的是i關于id 對稱得到的坐標,因為前面已經算過了mx前的每個點的回文串，所以，如果這個i點在mx范圍內，就將len[i]初始化為前面算過的數值while(str[i+len[i]]==str[i-len[i]])len[i]++;if(i+len[i]>mx) //mx為前i個回文子串的右端點所能到達的最大距離,即前面已經算過的最大回文區域mx=i+len[i],id=i;}int ans=0;for(int i=1;str[i];i++)ans=max(ans,len[i]);return ans-1; //回文串長度為len[i]-1,這個可以自己畫圖理解，因為s[]數組是在原串的基礎上插入了 '#' } int main(){while(~scanf("%s",s)){init();printf("%d\n",manacher());} }

?

　　

轉載于:https://www.cnblogs.com/00isok/p/9419714.html

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的hdu 3068 最长回文【manacher】(模板题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。