知識(shí)點(diǎn)

manacher算法可以在時(shí)間復(fù)雜度為O（n）的情況下，求出一個(gè)字符串的最長(zhǎng)回文子串的算法。

一 . 實(shí)現(xiàn)步驟

① 在字符串的各個(gè)字母中間加上一個(gè)字符，使其變成奇數(shù)字符串。對(duì)于原來(lái)是偶數(shù)字符串來(lái)說(shuō)，添加的字符“#”作為對(duì)稱中心；原來(lái)是奇數(shù)字符串的最中間的字母為對(duì)稱中心。

?② 設(shè)字符串的對(duì)稱中心為mid，r表示最長(zhǎng)回文串的右端點(diǎn)在哪里，i 表示當(dāng)前掃描到的節(jié)點(diǎn)，j 節(jié)點(diǎn)表示 i 節(jié)點(diǎn)關(guān)于字符串對(duì)稱中心對(duì)稱的位置。

---

模板題

洛谷 P3805 【模板】manacher 算法

題目描述

給出一個(gè)只由小寫(xiě)英文字符?組成的字符串?S?,求?S?中最長(zhǎng)回文串的長(zhǎng)度 。

字符串長(zhǎng)度為?n。

輸入格式

一行小寫(xiě)英文字符??組成的字符串?S。

輸出格式

一個(gè)整數(shù)表示答案。

輸入輸出樣例

輸入 #1

aaa

輸出 #1

3

說(shuō)明/提示

。

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #define ll long long using namespace std; const int maxn=1e8+5; char c[maxn<<1],s[maxn]; int p[maxn<<1]; int r,mid,ans=1; int main() {scanf("%s",s);int len=strlen(s);c[0]=c[1]='#';p[1]=1;for(int i=1;i<=len;++i){c[2*i]=s[i-1];c[2*i+1]='#';}c[(len<<1)+2]='$';//在各個(gè)字母之間加上字符進(jìn)行分割for(int i=0;i<(len<<1)+2;++i){if(i<r) p[i]=min(p[(mid<<1)-i],p[mid]+mid-i);else p[i]=1;while(c[i-p[i]]==c[i+p[i]]) p[i]++;if(p[i]+i>r){r=p[i]+i;mid=i;}}for(int i=0;i<=(len<<1)+2;++i){ans=max(ans,p[i]-1); }printf("%d",ans); return 0; }

相關(guān)練習(xí)

1 .?洛谷 P1659 [國(guó)家集訓(xùn)隊(duì)]拉拉隊(duì)排練

思路：由題得“連續(xù)的一段女生，有奇數(shù)個(gè)，并且他們手中的牌子所寫(xiě)的字母，從左到右和從右到左讀起來(lái)一樣，那么就被稱作和諧小群體” ，說(shuō)明需要找的這個(gè)字符串是回文字符串，可以使用manacher算法。又因?yàn)檎覍さ幕匚淖址淖址麄€(gè)數(shù)為奇數(shù)個(gè)，其實(shí)只需要在字符串首和尾部加上其他符號(hào)進(jìn)行特判即可。需要注意數(shù)據(jù)范圍很大，需要使用快速冪進(jìn)行加速運(yùn)算。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define ll long long #define re register using namespace std; ll int n,k; const int maxn=1e7+5,mod=19930726; char c[maxn],s[maxn<<1]; ll int p[maxn<<1],front[maxn]; ll int mid,r,len; inline ll int quick_pow(ll int x,ll int y) //快速冪加速 {ll int ans=1;while(y){if(y&1){ans=(ans*x)%mod;}x=(x*x)%mod;y>>=1;}return ans; }int main() {scanf("%d%d",&n,&k);scanf("%s",c+1);len=n;s[0]=s[1]='#';for(re ll int i=1;i<=len;++i){s[i<<1]=c[i];s[i<<1|1]='#';}len=(len<<1)+2;s[len]='$';for(re ll int i=1;i<len;++i){if(i<r) p[i]=min(p[(mid<<1)-i],r-i);else p[i]=1;while(s[i-p[i]]==s[p[i]+i]) p[i]++; //這里要注意是i-p[i]!!!if(p[i]+i>r){r=p[i]+i;mid=i;}if((p[i]-1)&1) front[p[i]-1]++; //用桶標(biāo)記有幾個(gè)奇數(shù)字符串}ll int sum=0,res=1;if(n%2==0) n--; //只需統(tǒng)計(jì)奇數(shù)的字符串for(re ll int i=n;i>=1;i-=2){sum+=front[i]; //統(tǒng)計(jì)有幾個(gè)和諧小群體if(sum<=k){res=(res*quick_pow(i,sum))%mod; //記錄前k個(gè)和諧小群體的女生個(gè)數(shù)的乘積k-=sum; }else{res=(res*quick_pow(i,k))%mod; break;}}if(sum<k) res=-1; //最后的總數(shù)也不能超過(guò)k，標(biāo)記為-1printf("%lld",res);return 0; }

2 .?洛谷 P4555 [國(guó)家集訓(xùn)隊(duì)]最長(zhǎng)雙回文串

思路：（待填坑）

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=1e6+5; char c[maxn<<1],s[maxn<<1]; int p[maxn<<1],len=0,r,mid,len1[maxn<<1],len2[maxn<<1]; //len1[i]表示以i開(kāi)頭的最長(zhǎng)回文串的長(zhǎng)度 //len2[i]表示以i結(jié)尾的最長(zhǎng)回文串的長(zhǎng)度 int main() {scanf("%s",c+1);len=strlen(c+1);s[0]=s[1]='#';for(int i=1;i<=len;++i){s[i<<1]=c[i];s[i<<1|1]='#';}len=(len<<1)+2;s[len]='$';for(int i=1;i<len;++i){if(i<r) p[i]=min(p[(mid<<1)-i],p[mid]+mid-i);else p[i]=1;while(s[i-p[i]] == s[i+p[i]]) p[i]++;if(p[i]+i>r) {mid=i;r=p[i]+i;}len1[i-p[i]+1]=max(len1[i-p[i]+1],p[i]-1); //求出以i開(kāi)頭的飽和回文串的最大長(zhǎng)度len2[i+p[i]-1]=max(len2[i+p[i]-1],p[i]-1); //求出以i結(jié)尾的飽和回文串的最大長(zhǎng)度}//求出以i開(kāi)頭的飽和與不飽和回文串的最大長(zhǎng)度f(wàn)or(int i=3;i<len;i+=2){len1[i]=max(len1[i],len1[i-2]-2); }//求出以i開(kāi)頭的飽和與不飽和回文串的最大長(zhǎng)度f(wàn)or(int i=len-1;i>=3;i-=2){len2[i]=max(len2[i],len2[i+2]-2);}int Max=0;for(int i=3;i<=len;i+=2){if(len1[i]&&len2[i]) //在同一節(jié)點(diǎn)能保證兩個(gè)子串都是回文串且總長(zhǎng)度最長(zhǎng)Max=max(Max,len1[i]+len2[i]);}printf("%d",Max);return 0; }

總結(jié)

以上是生活随笔為你收集整理的（待填坑）【字符串】manacher（马拉车）算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。