[模板]manacher

這麼簡單的算法現在才學......

https://segmentfault.com/a/1190000008484167?utm_source=tag-newest#articleHeader3

https://www.cnblogs.com/grandyang/p/4475985.html

1.在字符之間加入‘#’使得所有回文串的長度變成奇數，方便處理

2.p[i]數組記錄以 i 為回文中心最長回文的半徑，p[i]-1剛好就是這個串的長度

3.mr，id兩個變量，id為能延伸到最右端mr的回文子串的對稱軸，此時左端點為 mr*2-i，（這兩個變量和循環變量 i 無直接關系

4.核心代碼：

if (i < mr)

    p[i] = min(p[2 * id - i], mr - i);
else p[i]=1;

引用其他博客的圖片：

如果 mr - i > p[i]，那麼以 j 為中心的回文串包含在以 id 為中心的回文串里，又因為 i，j 對稱，這樣p[i]就肯定等於p[j]了

如果 mr-i <= p[i]，那麼綠框內至少是一樣的，外面的不知道，所以先設成綠框長度，以後在更新

如果 mr<=i，那麼就沒辦法了，只能從1開始算

最後接一個while暴力處理沒處理好的情況，在更新一下id和mr

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=;

char s[maxn];

char ss[maxn*];

int p[maxn*];//以i为中心最长回文半径

int init(){

    int len=strlen(s);

    ss[]='$';ss[]='#';

    int l=;

    for(int i=;i<len;i++){

        ss[l++]=s[i];

        ss[l++]='#';

    }

    ss[l]='\0';

    return l;//長度

}

int manacher()

{

    int len=init();

    int maxlen=-;//最長回文長度

    int id,mr=;//以id為中心最長回文右邊界mr，

    for(int i=;i<len;i++){

        if(i<mr)

        p[i]=min(p[*id-i],mr-i);

        else p[i]=;

        while(ss[i-p[i]] == ss[i+p[i]])//不需邊界判斷

        p[i]++;

        //每走一步i都比較一下，希望mr盡可能遠，更有機會執行i<mr的代碼提高效率

        if(mr<i+p[i])

        id=i,mr=i+p[i];

        maxlen=max(maxlen,p[i]-);

    }

    return maxlen;

}

int main()

{

    scanf("%s",s);

    printf("%d",manacher());

}

巴特西

[模板]manacher

最新文章

热门文章