Loading...

Manacher 学习笔记

check评论:0 条 remove_red_eye浏览量:361 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-03-23

ww

终于学了manacher,典型的题目是求出字符串中最长回文子串

首先是最最最暴力的方法,枚举左右,判断是否回文,时间复杂度$O(n^3)$

然后想到可以枚举中点,左右扩展,时间复杂度$O(n^2)$

想想第二种情况有哪些可以优化的地方

首先,奇数偶数长度,要分别讨论,这时,我们想到给两两字母之间加一个字符,比如$#$,这样就能全部变为奇数长度,可以快速找到对应点

其次,我们发现大部分的重复子串被多次计算,我们考虑用一个数组$qwq[i]$来记录以$i$为中点能扩展出的最长回文串

记录这些数据到$qwq$数组,同时记录一个$mid$,一个$mr$,分别代表已经确定的右侧最靠右的回文串的对称中心和右边界

然而,考虑一些情况,发现我们只能确认我们已知的回文串内的对称关系和回文半径等量关系,关于这个大回文串右侧,并没有数据,那么,当我们扫描到一个新的字符时,若当前扫描到的位置为i,若$mid\leq i\leq mr$,则我们可以找到它的一个对称点。这个点的位置是$(mid<<1)-i$

若扩展一个新的关于该字符的回文半径,可以先确定一部分$qwq[i]$

且我们知道,我们能确定的范围,其右侧不得大于$mr$,即:$qwq[i]+i\leq mr$

故$qwq[i]=min(qwq[(mid<<1)-i],mr-i)$

最后输出最大的$qwq[i]-1$即可

#include <bits/stdc++.h>
using namespace std;
char opt[102000010],a[51000010];
int n,qwq[102000010];
void getnew()
{
    opt[0]=opt[1]='#';
    n=strlen(a);
    for(int i=0;i<n;i++)
    {
        opt[(i<<1)+2]=a[i];
        opt[(i<<1)+3]='#';
    }
    n=(n<<1)+2;
    opt[n]=0;
}
void manacher()
{
    int mr=0,mid;
    for(int i=1;i<n;i++)
    {
        if(i<mr)
        {
            qwq[i]=min(qwq[(mid<<1)-i],mr-i);
        }
        else
        {
            qwq[i]=1;
        }
        for(;opt[i-qwq[i]]==opt[i+qwq[i]];qwq[i]++);
        if(qwq[i]+i>mr)
        {
            mr=qwq[i]+i;
            mid=i;
        }
    }
}
int main()
{
    scanf("%s",a);
    getnew();
    manacher();
    int ans=1;
    for(int i=0;i<n;i++)
    {
        ans=max(ans,qwq[i]);
    }
    cout<<ans-1;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名