Manacher算法+注釋

Manacher算法是用來求一個字符串中最長回文串的算法。

考慮暴力求最長回文串的做法:

暴力枚舉字符串中的所有字串判斷是否回文,然后求最大值。

時間復雜度O(n^3),考慮優化。

我們從枚舉所有字串改成枚舉所有回文串的對稱軸,向左右擴展直到不相等,得到最長回文串。

優化到O(n^2),還是不夠優秀。

于是我們引出Manacher算法。

先向字符串s中插入特殊字符得到字符串str,這樣我們就不用討論字符串長度是奇是偶了。

用一個輔助數組p表示每個點可以擴展出去的最長回文長度

從str[1]掃到str[strlen(str)],再設置兩個變量mr表示已觸及的最右邊的字符,mid表示包含mr的回文串的對稱軸位置。

當i屬于(mid,mr)時,顯然i關于mid的對稱點是(mid<<1)-i(中點坐標公式簡單推一下),由于回文串對稱串的全等性,我們令p[i]=p[(mid<<1)-i],然后接著嘗試擴展:str[i+p[i]]==str[i-p[i]](前后是否對稱),p[i]++

若i>mid,我們就設置mid=i,mr=當前擴展到的最右字符。

給出代碼結束本篇博客

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int data=0,w=1;char ch=0;
    while(ch!='-' && (ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0' && ch<='9')data=data*10+ch-'0',ch=getchar();
    return data*w;
}
const int maxn=5e7+10;
int n,p[maxn],ans;
char s[maxn],str[maxn];
void init(){
    str[0]=str[1]='$';//ccf喜歡這個 
    for(int i=0;i<n;i++)
        str[(i<<1)+2]=s[i],str[(i<<1)+3]='$';
    n=(n<<1)+2;
    str[n]=0;
}
void Manacher(){
    int mr=0,mid;
    for(int i=1;i<n;i++){
        if(i<mr)
            p[i]=min(p[(mid<<1)-i],p[mid]+mid-i);
        else p[i]=1;
        for(;str[i+p[i]]==str[i-p[i]];p[i]++);
        if(i+p[i]>mr)
            mr=p[i]+i,mid=i;
    }
}
int main(){
    scanf("%s",s);
    n=strlen(s);
    init();Manacher();
    ans=0;
    for(int i=0;i<n;i++)
        ans=max(ans,p[i]);
    printf("%d\n",ans-1);
    return 0;
}

下一篇更新一些數論知識

posted @ 2019-11-03 16:10  LightHouseOfficial  閱讀(...)  評論(...編輯  收藏
11选5走势图