BZOJ4650 || 洛谷P1117 [NOI2016]优秀的拆分【后缀数组】
时空限制 1000ms / 128MB
题目描述
如果一个字符串可以被拆分为 AABB的形式，其中 A和 B是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串aabaabaa，如果令 A=aab，B=a，我们就找到了这个字符串拆分成 AABB的一种方式。
一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令 A=a，B=baa，也可以用 AABB表示出上述字符串；但是，字符串 abaabaa就没有优秀的拆分。
现在给出一个长度为 n的字符串 S，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意：
出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
在一个拆分中，允许出现 A=B。例如 cccc 存在拆分 A=B=c
字符串本身也是它的一个子串。
输入格式：
每个输入文件包含多组数据。
输入的第一行只有一个整数 T，表示数据的组数。保证 1≤T≤10
接下来 T行，每行包含一个仅由英文小写字母构成的字符串 S，意义如题所述。
输出格式：
输出 T行，每行包含一个整数，表示字符串 SS 所有子串的所有拆分中，总共有多少个是优秀的拆分
说明
对于全部的测试点,保证 1≤T≤10。以下对数据的限制均是对于单组输入数据而言的，也就是说同一个测试点下的 T组数据均满足限制条件。
我们假定 n 为字符串 S的长度，每个测试点的详细数据范围见下表：
题目分析
不得不说数据范围设置无比清奇，算法95pts
可以考虑从这个的算法优化得到正解
令分别记录以位置开头/结尾 的 AA形式的字符串个数
那么有
正解瓶颈就在于这个rem数组怎么求
后缀数组当然是必要的，直接两两枚举A的开头再检查lcp长度是非常容易想的做法我觉得在考场上已经足够了
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
{
int len=j-i;
if(LCP(i,j)>=len&&j+len-1<=n)
rem[i][0]++,rem[j+len-1][1]++;
}
正确思路十分巧妙
我们先枚举AA串中A的长度，假如每个倍数的点上都打上标记
那么AA串一定正好经过两个打了标记的相邻的点
所以可以考虑计算每对相邻的点对rem数组的贡献
设这两个点为，那么
记
即求出后缀的lcp长度，以及前缀的lcs长度
当且仅当时这对相邻的点可以产生贡献
否则就会是像下面这样的情况
假如上述条件成立
那么AA串的结尾显然可以落在中间相交位置的任意位置，对应的开头也会落在长度相等的一段区间内
即这对相邻的点产生了的贡献
由于开头结尾可能的落点都是一个区间，所以用差分数组记录
最后求前缀和即得到了rem数组
这么做的复杂度为调和级数，即，约为妈呀这么难想考场上就不要这5分了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
typedef long long lt;
int read()
{
int x=0,f=1;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return x*f;
}
const int maxn=30010;
int T;
struct SA
{
int n,m;
int rak[maxn],tp[maxn],sa[maxn],tax[maxn];
int height[maxn],mi[maxn][17];
int a[maxn];
void init()
{
memset(rak,0,sizeof(rak));
memset(tp,0,sizeof(tp));
memset(sa,0,sizeof(sa));
memset(mi,0,sizeof(mi));
memset(height,0,sizeof(height));
memset(a,0,sizeof(a));
}
void rsort()
{
for(int i=0;i<=m;++i) tax[i]=0;
for(int i=1;i<=n;++i) tax[rak[i]]++;
for(int i=1;i<=m;++i) tax[i]+=tax[i-1];
for(int i=n;i>=1;--i) sa[tax[rak[tp[i]]]--]=tp[i];
}
void ssort()
{
m=127;
for(int i=1;i<=n;++i)
rak[i]=a[i],tp[i]=i;
rsort();
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(int i=n-k+1;i<=n;++i) tp[++p]=i;
for(int i=1;i<=n;++i) if(sa[i]>k) tp[++p]=sa[i]-k;
rsort();
swap(rak,tp);
rak[sa[1]]=p=1;
for(int i=2;i<=n;++i)
rak[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p;
if(p>=n)break;
m=p;
}
}
void getH()
{
int k=0;
for(int i=1;i<=n;++i)
{
if(k) k--;
int j=sa[rak[i]-1];
while(a[i+k]==a[j+k]) k++;
height[rak[i]]=k;
}
}
void RMQ()
{
for(int i=1;i<=n;++i) mi[i][0]=height[i];
for(int j=1;(1<<j)<=n;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
}
int LCP(int x,int y)
{
int ll=rak[x],rr=rak[y];
if(ll>rr) swap(ll,rr); ll++;
int k=0;
while((1<<k+1)<=rr-ll+1) k++;
return min(mi[ll][k],mi[rr-(1<<k)+1][k]);
}
}A,B;
int rem[maxn][2];
char txt[maxn];
int main()
{
T=read();
while(T--)
{
memset(rem,0,sizeof(rem));
scanf("%s",txt+1); int n=strlen(txt+1);
A.init(); B.init(); A.n=n; B.n=n;
for(int i=1;i<=n;++i)
A.a[i]=txt[i],B.a[i]=txt[n-i+1];//反着存一次s，方便求前缀的lcs
A.ssort(); A.getH(); A.RMQ();
B.ssort(); B.getH(); B.RMQ();
for(int len=1;len<=n/2;++len)
{
for(int i=len;i<=n;i+=len)
{
int j=i+len;
int lcp=min(A.LCP(i,j),len);
int lcs=min(B.LCP(n-i+2,n-j+2),len-1);
int tt=lcp+lcs-len+1;
if(lcp+lcs>=len)
{
rem[i-lcs][0]++; rem[i-lcs+tt][0]--;
rem[j+lcp-tt][1]++; rem[j+lcp][1]--;
}
}
}
for(int i=1;i<=n;++i)
rem[i][1]+=rem[i-1][1],rem[i][0]+=rem[i-1][0];
lt ans=0;
for(int i=1;i<n;++i)
ans+=rem[i+1][0]*rem[i][1];
printf("%lld\n",ans);
}
return 0;
}