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
 */

  转载请注明: Sshwy's Blog NOI2016 优秀的拆分

 上一篇
圆桌问题 圆桌问题
摘要 复习 Dinic~ 假设有来自 m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri (i =1,2,……,m)。 会议餐厅共有 n 张餐桌,每张餐桌可容纳 ci (i =1,2,……,n) 个代表就餐。 为了使代表
2019.04.11
下一篇 
[NOI2011] 阿狸的打字机 [NOI2011] 阿狸的打字机
摘要 好一个 AC 自动机 + 树状数组的题 打字机上只有 28 个按键,分别印有 26 个小写英文字母和’B’、’P’两个字母。经阿狸研究发现,这个打字机是这样工作的: 输入小写字母,打字机的一个凹槽中会加入这个字母 (这个字母加在
2019.04.10
  目录