BZOJ2342：[SHOI2011]双倍回文

时间：2020-12-15 13:46:31

浅谈\(Manacher\)：https://www.cnblogs.com/AKMer/p/10431603.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=2342

假设我已经将原字符串的\(p\)数组求好了。

双倍回文肯定是#\(W\)#\(W^R\)#\(W\)#\(W^R\)#

我们枚举中间一个#，求在它的回文半径的一半以内最靠前的第一个满足\(i+p_i-1\geqslant pos\)的第一个#，那么肯定第三个#也是存在的，然后用这个更新答案即可。

怎么快速找到第一个#呢？并查基优化即可。如果一个位置的\(i+p_i-1< pos\)那么显然这个位置也不可能作为后面的#号的第一个#，直接用并查基把他和下一个位置合起来即可。

时间复杂度：\(O(\alpha n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e6+5;

int n,ans;

char s[maxn];

int p[maxn],fa[maxn];

int read() {

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

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

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

	return x*f;

}

int find(int x) {

	if(fa[x]==x)return x;

	return fa[x]=find(fa[x]);

}

int main() {

	n=read();

	scanf("%s",s+1);

	for(int i=n;i;i--)

		s[i<<1]=s[i],s[(i<<1)-1]='#';

	s[n<<1|1]='#',s[0]='$',n=n<<1|1;

	int id=0,mx=0;

	for(int i=1;i<=n;i+=2)fa[i]=i;

	for(int i=1;i<=n;i++) {

		p[i]=i<=mx?min(mx-i+1,p[(id<<1)-i]):1;

		while(s[i-p[i]]==s[i+p[i]])p[i]++;

		if(i+p[i]-1>mx)id=i,mx=i+p[i]-1;

		if(s[i]=='#'&&p[i]>=5) {

			int st=i-p[i]/2;if(st%2==0)st|=1;

			for(int j=find(st);j<=i;j=find(j+2))

				if(j+p[j]<=i) fa[j]=find(j+2);

				else {ans=max(ans,(i-j)<<1);break;}

		}

	}

	printf("%d\n",ans);

	return 0;

}

根据洛谷一大佬的题解，此题有\(O(n)\)做法，只需要在\(mx\)被更新的时候枚举旧的\(mx\)到新的\(mx\)之间的点做双倍回文的右端点，新的\(id\)作为双倍回文的中点，然后判断对称过去是不是个回文即可。这样子做双倍回文肯定会被枚举到，并且枚举的总时间就是\(mx\)的改变量。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e6+5;

int n,ans;

int p[maxn];

char s[maxn];

int read() {

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

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

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

    return x*f;

}

int main() {

    n=read();

    scanf("%s",s+1);

    for(int i=n;i;i--)

        s[i<<1]=s[i],s[(i<<1)-1]='#';

    s[n<<1|1]='#',s[0]='$',n=n<<1|1;

    int id=0,mx=0;

    for(int i=1;i<=n;i++) {

        p[i]=i<=mx?min(mx-i+1,p[(id<<1)-i]):1;

        while(s[i-p[i]]==s[i+p[i]])p[i]++;

        if(i+p[i]-1>mx) {

            if(s[i]=='#') {

                int st=mx+1;if(s[st]!='#')st++;

                for(int j=st;j<=i+p[i]-1;j+=2) {

                    int pos=i+(j-i)/2;pos=(i<<1)-pos;

                    if(s[pos]=='#'&&p[pos]+pos-1>=i)ans=max(ans,j-i);

                }

            }

            id=i,mx=i+p[i]-1;

        }

    }

    printf("%d\n",ans);

    return 0;

}

相关文章