P4555 [国家集训队]最长双回文串 题解

以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • ZYyboT
    大佬大佬%%%%%%
  • rockyyh
    诶 为什么 rr[i]=max(rr[i],rr[i−2]−2) ll[i]=max(ll[i],ll[i+2]−2)
  • rockyyh
    哦哦 明白了 赞这个题解!
  • Modest_Man
    %%%rockyyh
  • up_grant
    讲解有点问题吧,rr[i]前面说是以i开头,但后面又说是以i结尾
  • wanghaoyu1008
    好!我就是用zyys这组数据找到bug的
  • guodong
    hack :abaca ??
  • guodong
    是我眼瞎。。。。。
  • 炮姐御坂美琴
    qaq
  • GLZP
    后面的rr[i]=max(rr[i],rr[i−2]−2)和ll[i]=max(ll[i],ll[i+2]−2)有什么意义呢?
作者: 浅色调 更新时间: 2018-05-25 22:16  在Ta的博客查看 举报    34  

Solution:

  本题$zyys$啊!~

  很容易想到$manacher$,于是先打个板子看看,处理出以$i$为中心的最长回文半径$p[i]$后,就断思路了。

  我首先想到的是,在每次更新$p[i]$后,分别处理出以$i$为中心的半径$p[i]$内,每个位置为开头和结尾的最长回文子串长度($manacher$结束后直接枚举断点就可以得到答案),但是这样强行又将复杂度拉到了$O(n^2)$。于是,开始断线~

  后面看看巨佬们的思路,豁然**,我是真的蠢啊~

  其实,将我开始的思路修改一下即可:

  我们维护最长回文半径$p[i]$的同时,再分别维护两个东西,以$i$为结尾的最长回文子串的长度$ll[i]$,和以$i$为开头的最长回文子串的长度$rr[i]$。

  那么很显然,因为以$i$为中心的最长回文子串长度为$p[i]-1$,所以每次更新$p[i]$后,我们只需处理出当前这个回文子串的左右边界(中间的每个点的$ll[i],rr[i]$可以在$manacher$结束后$O(n)$处理出),则$ll[i+p[i]-1]=max(ll[i+p[i]-1],p[i]-1)$(更新以$i+p[i]-1$为结尾的最长回文长度),同理$rr[i-p[i]+1]=max(rr[i-p[i]+1],p[i]-1)$。

  跑完$manacher$后,我们$O(n)$递推出每个'#'为断点的$ll[i]$和$rr[i]$,其中$rr[i]$因为是$i$结尾的回文长度,所以直接顺推,每往后移一位,最长回文子串长度$-2$,于是$rr[i]=max(rr[i],rr[i-2]-2)$($i-2$是上一个'#'位置),同理$ll[i]$直接逆推,类似地$ll[i]=max(ll[i],ll[i+2]-2)$。

  最后枚举每个'#'为断点,更新$ans$就$OK$了。

$\quad\;\;$欢迎来踩博客:five20(蒟蒻写题解不易,转载请注明出处~万分感谢!)

代码:

#include<bits/stdc++.h>
#define For(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define Bor(i,a,b,c) for(int (i)=(b);(i)>=(a);(i)-=(c))
#define Min(a,b) ((a)>(b)?(b):(a))
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=200050;
int p[N],ll[N],ans,rr[N],mx,id,cnt;
char s[N],t[N];
int main(){
    scanf("%s",t);
    int len=strlen(t);
    s[++cnt]='$',s[++cnt]='#';
    For(i,0,len-1,1)s[++cnt]=t[i],s[++cnt]='#';
    s[++cnt]='\0';
    For(i,1,cnt,1){
        if(i<mx)p[i]=Min(p[id*2-i],mx-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(mx<i+p[i])id=i,mx=i+p[i];
        ll[i+p[i]-1]=Max(ll[i+p[i]-1],p[i]-1);
        rr[i-p[i]+1]=Max(rr[i-p[i]+1],p[i]-1);
    }
    For(i,2,cnt,2)rr[i]=Max(rr[i],rr[i-2]-2);
    Bor(i,2,cnt,2)ll[i]=Max(ll[i],ll[i+2]-2);
    For(i,2,cnt,2)if(rr[i]&&ll[i])ans=Max(ans,ll[i]+rr[i]);
    cout<<ans;
    return 0;
}

评论

  • enceladus
    tql %%%% OTZ
  • Fraction
    赞!很简洁明了!
  • _ConveX
    我觉得l数组与r数组的定义应该是下面这样,l[i]表示包含i位置的所有回文串中心中最靠左的位置,r[i]表示包含i位置的所有回文串的中心中最靠右的位置,而且Ans=max(Ans,r[i]-l[i])。
  • AwwA
    这个题解是错的,qwe就能hack
  • AwwA
    啊好像没错
  • AwwA
    不对。。是写错了数据 qwq就能hack了
  • SSL_LRZ_MarMot
    楼上和空气斗智斗勇
  • Thomasguo666
    的确被hack了
  • SSL_LRZ_MarMot
    明白,我试过了 但气氛是真的尬
  • __wfx
    orz
作者: 顾z 更新时间: 2018-08-04 07:15  在Ta的博客查看 举报    18  

题目描述

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为abc,逆序为cba,不相同)。

输入长度为$n$的串$S$,求$S$的最长双回文子串$T$ ,即可将$T$分为两部分$X$,$Y$,

$($|X|$,$|Y|$\geq$1)且 $X$ 和 $Y$ 都是回文串。

分析

首先给出双回文串定义:

双回文串$A$是指一个可以被拆分成两个部分(B和C)的字符串 $A=B+C$, 且$B$和$C$都是回文串的串, A自己本身可以不是回文串.

看到回文很容易想到$manacher$算法

其实正解就是manacher (⊙o⊙)…

我相信大家都理解如何去处理字符串的奇偶,所以不再赘述~~

如果不会$manacher$还是先去敲板子-->manacher

过程:

因为双回文串是可以拼接得到的,

所以我们可以预先处理出来数组$RL[i]$

(即代表以$i$为对称轴的最大回文半径)

然后我们可以定义这么两个东西

1:$l[i]$代表$i$位置所在回文串中中心位置最左端的位置

2:$r[i]$代表$i$位置所在回文串中中心位置最右端的位置

我们可以算出来这两个个东西。

因此通过左右拼接就可以得到我们的双回文串

UPD:

2018.09.29.

感谢_ConveX指出一个天大的错误.

1.修改了$l$数组与$r$数组的定义.

2.并修改了部分代码,大家看着应该会舒服些

(可能排版不太好,请揍我谅解)

------------------ 代码------------------

#include<bits/stdc++.h>
#define IL inline
#define RI register int
#define N 100010
using namespace std;
char s[N<<1],ch[N];
int MaxRight,center,len;
int RL[N<<1],l[N<<1],r[N<<1];
int pos,ans;
int main()
{
    cin>>ch;
    len=strlen(ch);
    for(RI i=0;i<len;i++)s[2*i+1]=ch[i];
    len=2*len+1;//这里不要忘记变化长度! 
    RL[0]=1;
    for(RI i=1;i<len;i++)
    {
        if(i<=MaxRight)
            RL[i]=min(MaxRight-i,RL[2*center-i]);
        else 
            RL[i]=1;
        while(i-RL[i]>=0&&RL[i]+i<len&&s[i+RL[i]]==s[i-RL[i]])
                            ++RL[i];
        if(i+RL[i]-1>MaxRight)
            MaxRight=i+RL[i]-1,center=i;//注意更新操作 
    }
    for(RI i=0;i<len;i++)
        for(;pos<=i+RL[i]-1;pos++)
            l[pos]=i;//概念和上面讲的一样 
    pos=len;
    for(RI i=len-1;i>=0;i--)
        for(;pos>=i-RL[i]+1;pos--)
            r[pos]=i;//概念同上面讲的一样 
    for(RI i=0;i<len;i++)
        ans=max(ans,r[i]-l[i]);//为了保险 ,貌似可以直接减 emmm 
    cout<<ans;
}

如果哪里写的好 请私信我emmm

评论

  • Andrew82
    回文自动机是神马东西
  • qcwlmqy
    回文自动机是好东西
  • wangzhifang
    1楼-2楼:神马=好
作者: foreverlastnig 更新时间: 2018-07-08 20:09  在Ta的博客查看 举报    13  

回文自动机裸题。

分别建两个回文自动机,一个是正序,一个是倒序,然后通过自动机得出最长回文长度,接着枚举切割点就好了。

2018.12.15update:之前忘记考虑不切割的情况,那只要不枚举$n$为切割点就好了。

code:

//2018.11.21 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
    res s=0;
    bool w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void _swap(res &x,res &y){
    x^=y^=x^=y;
}
inline int _abs(const res &x){
    return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
    return x>y?x:y;
}
inline int _min(const res &x,const res &y){
    return x<y?x:y;
}
const int N=1e5+10;
namespace MAIN{
    int n;
    int a[N],b[N];
    struct PAM{
        struct Pam{
            int vis[26],len,fail;
        }pam[N];
        int las,cnt;
        PAM() {pam[1].fail=pam[0].fail=1,pam[cnt=1].len=-1;}
        inline void extend(const res &x,const res &id,char *str){
            res p=las;
            for(;str[id-pam[p].len-1]!=str[id];p=pam[p].fail);
            if(!pam[p].vis[x]){
                res np=++cnt,q=pam[p].fail;
                for(;str[id-pam[q].len-1]!=str[id];q=pam[q].fail);
                pam[np].fail=pam[q].vis[x],pam[p].vis[x]=np,pam[np].len=pam[p].len+2;
            }
            las=pam[p].vis[x];
        }
    }A,B;
    char str[N];
    int ans;
    inline void MAIN(){
        scanf("%s",str+1);
        n=strlen(str+1);
        for(res i=1;i<=n;i++)A.extend(str[i]-'a',i,str),a[i]=A.pam[A.las].len;
        reverse(str+1,str+n+1);
        for(res i=1;i<=n;i++)B.extend(str[i]-'a',i,str),b[n-i+1]=B.pam[B.las].len;
        for(res i=1;i<n;i++)ans=_max(a[i]+b[i+1],ans);
        printf("%d\n",ans);
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}

评论

  • ez_lcw
    还没有评论
  • 松风之狐
    THD
作者: 楚泫  更新时间: 2019-02-27 19:45  在Ta的博客查看 举报    10  

初学Manacher,写给和自己一样的小白们


下午刚学了 $Manacher$ ,做到这题。

然后对于大佬们的题解做一个更为详细的补充说明,

主要针对自己的一些疑惑,以及不理解的地方做了详尽的诠释

顺手就全写代码里了!有哪里讲的不清楚可以问窝(虽然我很弱


#include <bits/stdc++.h>
#define ll long long
#define space putchar(' ')
#define endl putchar('\n')
#define debug puts("------------------------")
using namespace std;
inline void read(int &a) {a = 0; int c = getchar(), b = 1; while (c > '9' || c < '0') {if (c == '-')b = -1; c = getchar();} while (c >= '0' && c <= '9') a = (a << 3) + (a << 1) + c - 48, c = getchar(); a *= b; }
inline int  Rem() {int a = 0, c = getchar(), b = 1; while (c > '9' || c < '0') {if (c == '-')b = -1; c = getchar();} while (c >= '0' && c <= '9') a = (a << 3) + (a << 1) + c - 48, c = getchar(); return a *= b; }
inline void write(int x) {if (x > 9)write(x / 10); putchar('0' + x % 10);}
inline void W(int x) {if (x < 0) {putchar('-'), x = -x;} write(x);}
/**/
const int N = 11000005;
char a[N], s[N << 1];
int n, hw[N << 1], ans, l[N << 1], r[N << 1];
/**/
void Pre()//非常模板的插入
{
    s[0] = '#';
    s[1] = '$';
    int cnt = 1;
    for (int i = 1; i <= n; i++)
    {
        s[++cnt] = a[i];
        s[++cnt] = '$';
    }
    n = (n << 1) + 2;
    s[n] = '~';
}

void work()//同样非常模板的Manacher
{
    int mr = 0, mid;
    for (int i = 1; i <= n; i++)
    {
        if (i < mr) hw[i] = min(hw[(mid << 1) - i], mr - i);
        else hw[i] = 1;
        while (s[i + hw[i]] == s[i - hw[i]]) ++hw[i];
        if (hw[i] + i > mr) mr = hw[i] + i, mid = i;
        /**
         * l[i]表示以i为左端点的最长的回文串
         * r[i]表示以i为右端点的最长的回文串
         *
         * 对于蒟蒻(我)来讲有点抽象所以我们举一个生动的栗子:
         *
         *      首先,字符串为ababaccd
         *
         *                0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17
         *      插入后变成 #|$|a|$|b|$|a|$|b|$|a |$ |c |$ |c |$ |d |~
         *
         *      显然i = 4时,hw[4] = 4
         *      L = 7 = i + hw[4]-1;
         *      R = 1 = i-hw[4]+1;
         *      回文串实际长度=hw[4]-1;
         *      所以转移就是: l[i+hw[i]-1]=max(l[i+hw[i]-1],hw[i]-1);
         *                   r[i-hw[i]+1]=max(r[i-hw[i]+1],hw[i]-1);
         *
         */
        r[i + hw[i] - 1] = max(r[i + hw[i] - 1], hw[i] - 1);
        l[i - hw[i] + 1] = max(l[i - hw[i] + 1], hw[i] - 1);
    }
}

int main()
{
    scanf("%s", a + 1);
    n = strlen(a + 1);
    Pre();
    work();
/**
 *  又因为两块不能重叠,所以我们选择'$'作为断点进行枚举
 *
 *  那么先提出一个困扰蒟蒻我的问题:
 * 
 *  Q: 上面不是已经求过了吗,为什么还要递推呢?
 *
 *  A: 上面求出的每个l[i]和r[i]都是在i最大的情况下求的
 *      
 *      eg:0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17
 *         #|$|a|$|b|$|a|$|b|$|a |$ |c |$ |c |$ |d |~
 *
 *      l[3]求出来的是0,但很明显bab是一个回文,l[3]应该等于3
 *      这是因为我们在i=6时,hw[i]=6,只更新了l[1]和r[11],因为bab不是i=6的最长回文串所以没有更新
 *
 *      这时就需要递推把前面的转移过来了:
 *
 *          bab 比 ababa 短两个字符。
 *          每一个回文串向后挪动一个 都会少两个字符,所以:
 *          l[i] = max(l[i], l[i - 2] - 2);
 *          r[i] = max(r[i], r[i + 2] - 2);
 *          我们枚举的是'$'的位置,所以l[i]正推由前一个'$'的位置转移来,r[i]逆推由后面的'$'转移来,每次都会-2回文串长度
 *
 */
    for (int i = n; i >= 1; i -= 2) r[i] = max(r[i], r[i + 2] - 2);
    for (int i = 1; i <= n; i += 2) l[i] = max(l[i], l[i - 2] - 2);

    for (int i = 1; i <= n; i += 2) if (r[i] && l[i]) ans = max(ans, l[i] + r[i]);
    W(ans);
    return 0;
}

评论

  • AThousandSuns
    PAM大佬%%%
  • AThousandSuns
    PAM大佬%%%
  • newblash
    %%%dalao
  • lyslys
    %%%dalao
作者: AThousandMoon 更新时间: 2018-12-12 14:09  在Ta的博客查看 举报    5  

题意:求字符串的最长子串$S$满足可以分为$X,Y$,使得$X,Y$都是回文串。

设$l[i],r[i]$分别为以第$i$个字符为开头(结尾)的回文子串最长可以,则$ans=\max_{i=0}^{n-2}(r[i]+l[i+1])$.

至于求$l,r$,我们使用回文树把正序和反序都做一遍,每次把这个节点代表的回文子串的长度返回就可以了。

至于manacher,...那是什么神仙东西(大雾

#include<cstdio>
#include<cstring>
#include<algorithm>
#define Rint register int
using namespace std;
const int N = 100003;
struct Palindrome_Automaton {
    int ch[N][26], fail[N], cnt[N], len[N], S[N], n, p, last;
    inline int newnode(int l){
        for(Rint i = 0;i < 26;i ++)
            ch[p][i] = 0;
        cnt[p] = 0;
        len[p] = l;
        return p ++;
    }
    inline void init(){
        p = 0;
        newnode(0); newnode(-1);
        n = last = 0;
        S[n] = -1;
        fail[0] = 1;
    }
    inline int getfail(int x){
        while(S[n - len[x] - 1] != S[n]) x = fail[x];
        return x;
    }
    inline int insert(int c){
        S[++ n] = c;
        int cur = getfail(last);
        if(!ch[cur][c]){
            int now = newnode(len[cur] + 2);
            fail[now] = ch[getfail(fail[cur])][c];
            ch[cur][c] = now;
        }
        last = ch[cur][c];
        cnt[last] ++;
        return len[last];
    }
} pa;
int n, l[N], ans;
char str[N];
int main(){
    scanf("%s", str);
    n = strlen(str);
    pa.init();
    for(Rint i = n - 1;~i;i --)
        l[i] = pa.insert(str[i] - 'a');
    pa.init();
    for(Rint i = 0;i < n - 1;i ++)
        ans = max(ans, l[i + 1] + pa.insert(str[i] - 'a'));
    printf("%d", ans);
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。