BZOJ 2342: [Shoi2011]双倍回文马拉车算法/并查集

2023-02-21 07:46:34

2342: [Shoi2011]双倍回文

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1123 Solved: 408

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=2342

Description

输入分为两行，第一行为一个整数n，表示字符串的长度，第二行有n个连续的小写的英文字符，表示字符串的内容。

Input

输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。

Output

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

Sample Input

16
ggabaabaabaaball

Sample Output

HINT

题解：

用传说中的马拉车算法，算出所有的回文中心，以及P数组，然后我们就枚举i-(i-p[i])/2位置到第i位置的p[j]是否大于i

然后如果大于就说明这是一个双倍回文

但是，这样子会T，那么我们肿么优化呢？

那就献祭出并查集吧~！

♪(^∇^*)，100ms就跑过去啦

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 500005

#define mod 10007

#define eps 1e-9

const int inf=0x7fffffff;   //无限大

/*

*/

//**************************************************************************************

char s[maxn];

char str[maxn*];

int p[maxn*];

int fa[maxn*];

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int l;

int manacher(char s[],int l)

{

   int i,j,k,ans=;

   for(i=;i<=l;++i)str[i<<]=s[i],str[(i<<)+]='#';

   str[]='#';str[l*+]='#';str[]='&';str[l*+]='$';

   l=l*+;j=;

   for(i=;i<=l;)

   {

       while(str[i-j-]==str[i+j+])++j;

       p[i]=j;if(j>ans)ans=j;

       for(k=;k<=j&&p[i]-k!=p[i-k];++k)p[i+k]=min(p[i-k],p[i]-k);

       i+=k;j=max(j-k,);

   }

   return ans;

}

int get(int p)

{

    if(fa[p]==p)

        return p;

    fa[p]=get(fa[p]);

    return fa[p];

}

int main()

{

    l=read();

    scanf("%s",s+);

    manacher(s,l);

    l=l*+;

    for(int i=;i<=l;i++)

    {

        if(str[i]=='#')

            fa[i]=i;

        else

            fa[i]=i+;

    }

    int j;

    int ans=;

    for(int i=;i<l;i+=)

    {

        j=get(max(i-p[i]/,));

        for(;j<i&&j+p[j]<i;fa[j]=get(j+),j=fa[j]);

        if(j<i)

            if((i-j)*>ans)

            ans=(i-j)*;

    }

    cout<<ans<<endl;

}

码农公寓