ACM模板

---

目錄

• • • 初始化以及構造

初始化以及構造

數組下標從1開始即cin>>s+1
由于奇回文串和偶回文串某些性質不同，我們首先通過init()操作使得新串中所有回文串的長度都變成奇數，返回值是新串的長度（原串中的下標i對應新串中的2i）

定義數組p[]，p[i]表示新串中以下標i為回文中心的最大回文半徑。

新串中每一個下標的i意味著原串中存在一個的長度是p[i]-1的回文串

時間復雜度：$O(n)$

const int N=2000010; char s[2*N]; int p[2*N]; int init(char s[]) {int n=strlen(s+1);for(int i=2*n;i;i-=2){s[i]=s[i/2];s[i-1]='*';}s[2*n+1]='*';s[0]='@',s[2*n+2]='&';//哨兵return 2*n+1; } int manacher(int n)// 新串的長度 {int res=0;int now=0,mx=0;for(int i=1;i<=n;i++){p[i]=i<mx?min(p[2*now-i],mx-i):1;while(s[i+p[i]]==s[i-p[i]]) p[i]++;if(i+p[i]>mx){mx=i+p[i];now=i;}res=max(res,p[i]-1);//返回最大回文長度}return res; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【模板】Manacher算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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