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

蒟蒻初音ミク · 2019-07-10 17:11:53 · 题解

正文

这道题的具体做法本蒟蒻在这里不多作阐释，因为本蒟蒻的做法与前面大佬的做法是一样的，这篇题解也是为了解答浅色调大佬未给大家解答的一个问题（注意打斜杠的两行代码）：

//因为每个双回文串中间不能交叉，所以只能枚举'#'来找答案 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}

#define re register
#define ll long long
#define N 100100

int n,len[(N<<1)+10],l[(N<<1)+10],r[(N<<1)+10];
//l[i]表示以i结尾的最长回文串的长度
//r[i]表示以i开头的最长回文串的长度 
char ch[N+10],s[(N<<1)+10];
//ch是原数组，s是中间加了'#'的数组

void manache()
{
    int id=0,maxx=0;
    for(re int i=1;i<=n;++i)
    {
        if(i<maxx)len[i]=min(maxx-i,len[id*2-i]);
        else len[i]=1;
        while(s[i+len[i]]==s[i-len[i]])++len[i];
        if(i+len[i]>maxx)
        {
            maxx=i+len[i];
            id=i;
        }
        l[i+len[i]-1]=max(l[i+len[i]-1],len[i]-1);//回文串真实长度为len[i]-1 
        r[i-len[i]+1]=max(r[i-len[i]+1],len[i]-1);
    }
}

int main()
{
    scanf("%s",ch+1);
    int tlen=strlen(ch+1);
    s[0]='$';s[1]='#';n=1;
    for(re int i=1;i<=tlen;++i)
    {
        s[++n]=ch[i];
        s[++n]='#';
    }
    manache();
    for(re int i=3;i<=n;i+=2)r[i]=max(r[i],r[i-2]-2);////////
    for(re int i=n;i>=3;i-=2)l[i]=max(l[i],l[i+2]-2);////////
    int ans=0;
    for(re int i=3;i<=n;i+=2)if(r[i]&&l[i])ans=max(ans,l[i]+r[i]);//一定要写r[i]&&l[i]，否则会wa 
    printf("%d\n",ans);
    return 0;
}

路过的读者大大有很多都因为不理解打斜杠的两句而发表评论求解，本蒟蒻今天就告诉大家这两句的意义吧。

首先明确两个东西：饱和回文串和不饱和回文串

定义如图：

那么刚才的代码当中manache函数貌似已经计算了每一个字符作为开头和结尾的最大长度，但是仔细一想就可以发现，这只是计算了每一个字符作为开头和结尾的饱和回文串的长度！！！因为len[i]-1实际上指的是原数组中以i为中心的饱和回文串的长度！！！

那么，为了计算每一个字符作为不饱和字符串开头和结尾的长度，上面的代码中便加上了两行：

for(re int i=3;i<=n;i+=2)r[i]=max(r[i],r[i-2]-2);
for(re int i=n;i>=3;i-=2)l[i]=max(l[i],l[i+2]-2);

为什么i+=2？？？为什么l[i+2]-2？？？我们来看一下。

首先，双回文串的两端不能有交叉的地方，所以我们找到的双回文串的断点必须是'#'，而每一个'#'中间间隔一个字符，所以要i+=2

其次，关于l[i]=l[i+2]-2的问题，我们来画图：

从图中可以看出，对于i来讲，因为他是'#'，所以它在原来的数组中是处于夹缝中的，那么以它结尾的不饱和回文串的最大长度=以i+2结尾的回文串的最大长度-2

即l[i]=l[i+2]-2

那么以此类推，r[i]也是一样的：

所以，总代码便是：

code：

//因为每个双回文串中间不能交叉，所以只能枚举'#'来找答案 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int min(int a,int b){return a<b?a:b;}//手写min函数
inline int max(int a,int b){return a>b?a:b;}//手写max函数

#define re register
#define ll long long
#define N 100100

int n,len[(N<<1)+10],l[(N<<1)+10],r[(N<<1)+10];
//l[i]表示以i结尾的最长回文串的长度
//r[i]表示以i开头的最长回文串的长度 
char ch[N+10],s[(N<<1)+10];
//ch：原数组，s：加了'#'的数组

void manache()//manacher求最长回文串的函数
{
    int id=0,maxx=0;
    for(re int i=1;i<=n;++i)
    {
        if(i<maxx)len[i]=min(maxx-i,len[id*2-i]);
        else len[i]=1;
        while(s[i+len[i]]==s[i-len[i]])++len[i];
        if(i+len[i]>maxx)
        {
            maxx=i+len[i];
            id=i;
        }
        l[i+len[i]-1]=max(l[i+len[i]-1],len[i]-1);//求出以i结尾的饱和回文串的最大长度
        r[i-len[i]+1]=max(r[i-len[i]+1],len[i]-1);//求出以i开头的饱和回文串的最大长度
    }
}

int main()
{
    scanf("%s",ch+1);
    int tlen=strlen(ch+1);
    s[0]='$';s[1]='#';n=1;
    for(re int i=1;i<=tlen;++i)
    {
        s[++n]=ch[i];
        s[++n]='#';
    }
    manache();
    for(re int i=3;i<=n;i+=2)r[i]=max(r[i],r[i-2]-2);//求出以i开头的饱和与不饱和回文串的最大长度
    for(re int i=n;i>=3;i-=2)l[i]=max(l[i],l[i+2]-2);//求出以i结尾的饱和与不饱和回文串的最大长度
    int ans=0;
    for(re int i=3;i<=n;i+=2)if(r[i]&&l[i])ans=max(ans,l[i]+r[i]);//一定要写r[i]&&l[i]，否则会wa 
    printf("%d\n",ans);
    return 0;
}

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

广告

正文

code：