P4287 [SHOI2011]双倍回文(回文树)

题目描述

记字符串 w 的倒置为 w^R 。例如 (abcd)^R=dcba , (abba)^R=abba 。

对字符串x，如果 x 满足 x^R=x ，则称之为回文；例如abba是一个回文，而abed不是。

如果x能够写成的 ww^Rww^R 形式，则称它是一个“双倍回文”。换句话说，若要 x 是双倍回文，它的长度必须是 \(4\) 的倍数，而且 x ， x 的前半部分， x 的后半部分都要是回文。例如 abbaabba 是一个双倍回文，而 abaaba 不是，因为它的长度不是4的倍数。

x 的子串是指在 x 中连续的一段字符所组成的字符串。例如 \(be\) 是 \(abed\) 的子串，而 \(ac\) 不是。

x 的回文子串，就是指满足回文性质的 x 的子串。

x 的双倍回文子串，就是指满足双倍回文性质的 x 的子串。

你的任务是，对于给定的字符串，计算它的最长双倍回文子串的长度。

输入输出格式

输入格式：

输入分为两行。

第一行为一个整数，表示字符串的长度。

第二行有个连续的小写的英文字符，表示字符串的内容。

输出格式：

输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出 \(0\) 。

输入输出样例

输入样例#1： 复制

16

ggabaabaabaaball

输出样例#1： 复制

说明

N \(\le\) 500000

题解

一道海星的回文树思维题。

其实ww^Rww^R要是回文串。

w=w^R。所以其实就是先找出一个ww^R，然后保存，然后看后面是否还能接着找到一个ww^R。如果找到了就验证它们的长度能否被四整除就OK了。

当然我们又引进了一个新的数组half，这个数组表示以这个节点为回文串结尾，回文串中间的节点的位置。但是回文串自己本身并不保证一定让half成立。所以我们还需要在统计时验证一下答案是否合理。

代码

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

int len;

char s[500050];

struct node{

    int fail,len,ch[26],half;

}t[500050];

int read()

{

    int x=0,w=1;char ch=getchar();

    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*w;

}

void solve()

{

    int k=0,tot=1;

    t[1].fail=t[0].fail=1;t[1].len=-1;

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

    {

        while(s[i-t[k].len-1]!=s[i])k=t[k].fail;

        if(!t[k].ch[s[i]-'a']){

            t[++tot].len=t[k].len+2;

            int j=t[k].fail;

            while(s[i-t[j].len-1]!=s[i])j=t[j].fail;

            t[tot].fail=t[j].ch[s[i]-'a'];

            t[k].ch[s[i]-'a']=tot;

            if(t[tot].len==1)t[tot].half=0;

            else {

                int pos=t[k].half;

                while(s[i-t[pos].len-1]!=s[i]||(t[pos].len+2)*2>t[tot].len)

                pos=t[pos].fail;

                t[tot].half=t[pos].ch[s[i]-'a'];

            }

        }

        k=t[k].ch[s[i]-'a'];

    }

}

int main()

{

    scanf("%d%s",&len,s);

    solve();

    int ans=0;

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

    if(t[i].len%4==0&&t[t[i].half].len*2==t[i].len)ans=max(ans,t[i].len);

    cout<<ans<<endl;

    return 0;

}

巴特西

P4287 [SHOI2011]双倍回文(回文树)

题目描述

输入输出格式

输入输出样例

说明

题解

代码

最新文章

热门文章