NOI2016优秀的拆分

摘要

人生第二道黑题~

如果一个字符串可以被拆分为AABB的形式,其中 A和 B是任意非空字符串,则我们称该字符串的这种拆分是优秀的。例如,对于字符串aabaabaa,如果令 A=aab,B=a,我们就找到了这个字符串拆分成 AABB的一种方式。

一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=a,B=baa,也可以用 AABB表示出上述字符串;但是,字符串 abaabaa 就没有优秀的拆分。

现在给出一个长度为 n的字符串S,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意:

  1. 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
  2. 在一个拆分中,允许出现A=B。例如 cccc 存在拆分A=B=c。
  3. 字符串本身也是它的一个子串。

多组数据, .

一道暴力95分正解5分的题

求AA

考虑如何快速求一个字符串中的AA形式的子串。对字符串 建立后缀数组,可以在 的时间内求解任意后缀的LCP,或者任意前缀的LCS(反向建一个).

对于两个位置 ,如果这两个位置上的字符匹配,那么这两个位置可能包含在AA型的子串中,而我们计算这两个位置的LCP,LCS

p1

如果LCP,LCS有重合部分,那么这个重合部分就是AA的分界范围,举个例子:

aabaabaa,取 ,此时 ,两者重合,因此分界线在 范围内,对应的AA型的子串分别为 .

因此对于位置 我们可以 求出分界的范围,进而得出和 有关的AA型子串。

求AABB

有了AA型子串怎么求AABB?显然,我们只需要知道以 结尾的有多少个AA子串,以 开头的有多少个AA,然后两者相乘就是以 分界的AABB的个数啦

对于位置 求得了AA的分界线范围,就可以顺便求得它的贡献的左端点和右端点的范围,差分一下记录在数组里,最后两个数组分别处理前缀和,后缀和,然后一起统计即可。

如何高效枚举 使得求出的AA不重不漏?我们枚举步长 ,然后只需要枚举 的位置即可。对于求出的分界线范围,我们强制限定它在 中间,这样就保证了不重不漏。

根据调和级数,枚举的复杂度

处理一个位置的复杂度是 的。加上预处理SA的复杂度,总复杂度仍为 .

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;

struct SA{
char s[N];
int l;
int sa[N],rk[N];
int t[N],bin[N],sz;
int h[N];//h,height
void clear(){
memset(h,0,sizeof(h));
memset(t,0,sizeof(t));
memset(sa,0,sizeof(sa));
memset(rk,0,sizeof(rk));
sz=l=0;
}
void qsort(){
for(int i=0;i<=sz;i++)bin[i]=0;
for(int i=1;i<=l;i++)bin[rk[t[i]]]++;
for(int i=1;i<=sz;i++)bin[i]+=bin[i-1];
for(int i=l;i>=1;i--)sa[bin[rk[t[i]]]--]=t[i];
}
void make(){
l=strlen(s+1),sz=max(l,26);
for(int i=1;i<=l;i++)t[i]=i,rk[i]=s[i]-'a'+1;
qsort();
for(int j=1;j<=l;j<<=1){
int tot=0;
for(int i=l-j+1;i<=l;i++)t[++tot]=i;
for(int i=1;i<=l;i++)if(sa[i]-j>0)t[++tot]=sa[i]-j;
qsort();
swap(t,rk);
rk[sa[1]]=tot=1;
for(int i=2;i<=l;i++)
rk[sa[i]]=t[sa[i-1]]==t[sa[i]]&&t[sa[i-1]+j]==t[sa[i]+j]?tot:++tot;
}
}
int move(int x,int y,int len){
while(x+len<=l&&y+len<=l&&s[x+len]==s[y+len])++len;
return len;
}
void calc_h(){
for(int i=1;i<=l;i++)
h[i]=rk[i]==1?0:move(i,sa[rk[i]-1],max(h[i-1]-1,0));
}
int st[N][16];//h[sa[i]]~h[sa[i+2^j]]中的最小值
void make_st(){
for(int i=1;i<=l;i++)st[i][0]=h[sa[i]];
for(int j=1;(1<<j)<=l;j++){
int step=1<<(j-1);
for(int i=1;i+step<=l;i++){
st[i][j]=min(st[i][j-1],st[i+step][j-1]);
}
}
}
int lcp(int x,int y){//返回长度
if(x==y)return l-x+1;
x=rk[x],y=rk[y];
if(x>y)swap(x,y);
x++;//取不到x
int step=log(y-x+1)/log(2);
return min(st[x][step],st[y-(1<<step)+1][step]);
}
void go(char *_s){//打包
memcpy(s,_s,sizeof(s));
make(),calc_h(),make_st();
//for(int i=1;i<=l;i++)printf("%d ",sa[i]);puts("");
}
};
SA sa,rv;//正反两个SA
int t;
char s[N];
void solve(){
sa.clear(),rv.clear();
sa.go(s);
reverse(s+1,s+sa.l+1);
rv.go(s);
const int l=sa.l;
int v1[N]={0},v2[N]={0};//左右两个贡献,v1是后缀和,v2是前缀和
for(int step=1;step<=l;step++){//枚举步长
for(int i=1;i+step<=l;i+=step){//i,i+step
int lcp=sa.lcp(i,i+step),lcs=rv.lcp(l-i+1,l-i-step+1);
if(lcp+lcs-1<step)continue;
int L=max(1,i-min(step,lcs)+1),R=min(i+step+min(lcp,step)-1,l);
int tot=R-L+1-step*2+1;//贡献的左端点区间为[L,L+tot),右端点区间为(R-tot,R]
v1[L+tot-1]++,v1[L-1]--;
v2[R-tot+1]++,v2[R+1]--;
}
}
for(int i=l;i>=1;i--)v1[i]+=v1[i+1];
for(int i=1;i<=l;i++)v2[i]+=v2[i-1];
long long res=0;
for(int i=2;i<=l;i++)res+=(long long)v1[i]*v2[i-1];
printf("%lld\n",res);
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%s",s+1);
solve();
}
return 0;
}
/*
* BUG#1: bin[i-1]写成bin[i+1]
* 求后缀(i,j)(rk[i]<rk[j])的LCP,就是求 j in (rk[i],rk[j]] 的height[j] 的最小值,即RMQ.
* 求前缀(i,j)的LCS,就是在反串上求(l-i+1,l-j+1)两个后缀的LCP
* BUG#2: 数组没有初始化为0
* BUG#3: res没开ll
*/