Border Theory 学习笔记

· · 题解

若字符串 s 的某个非空真前缀 s[1…i] 恰是该字符串的后缀，则称 i 是 s 的一个公共前后缀，即一个 Border。

若字符串 s 满足 \forall i\le |S|-t,s[i+t]=s[i]，则称正整数 t 是字符串 s 的一个周期。

定理 0：若 i 是 s 的一个 Border，则 |S|-i 是 s 的一个周期。

证明：由于 i 是 s 的一个 Border，得到 \forall p\le i,s[p+|S|-i]=s[p]。稍作变形可得 \forall p\le |S|-(|S|-i),s[p+(|S|-i)]=s[p]，符合周期定义，得证。

定理 1（弱周期定理，Weak Periodicity Lemma，WPL）：若 p,q 都是字符串 s 的周期，且 p+q\le |S|，则 (p,q) 也是字符串 s 的一个周期。

证明：不妨设 p>q。设 d=p-q，试说明 d 也是字符串 s 的一个周期。

证毕。

还有强周期定理：若 p,q 都是字符串 s 的周期，且 p+q-(p,q)\le |S|，则 (p,q) 也是字符串 s 的一个周期。笔者不会证明。一般来说用不到。

推论：将上述前缀 p 和前缀 q 复制无限多次，形成的字符串是相同的。

证明：gcd 性质易证。

定理 2：对于所有 s 的 \ge \lfloor\frac{|S|}{2}\rfloor 的 Border，它们与 |S| 共同构成一个等差数列。

证明：考虑两个 Border |S|-p,|S|-q\ge \lfloor\frac{|S|}{2}\rfloor。则 p+q\le|S|。设 |S|-p 是最大的 Border。根据定理 0，我们可以得到 s 的两个周期 p,q。由定理 1，得到 (p,q) 也是一个周期。又因为 p 是最大的 Border，故 (p,q)=p，即 q 是 p 的倍数。同时，周期的整数倍也一定都是周期，所以我们得到所有的 p 的倍数都是周期。因此，一个满足条件的 q 是周期等价于它是 p 的倍数。所以所有的满足条件的 Border 恰构成一个公差为 p 的等差数列，证毕。

定理 3：将所有 Border 按其二进制最高位进行分段，每一段内的 Border 都构成一个等差数列。

证明：设 [2^i,2^{i+1}) 中最大的 Border 为 p。那么段内的其余 Border 都是 s[1…p] 的 Border，且其长度 \ge\lfloor\frac{p}{2}\rfloor 。根据定理 2，它们是一个等差数列。证毕。

因此，我们可以将 s 的所有 Border 排序后划分为 \lceil\log_2{|S|}\rceil 个在值域上不交的等差数列。

例题：[WC2016] 论战捆竹竿

题意：给定一个串 s，求其 Border 集合进行线性组合能够得到多少个 \le w-|S| 的值。|S|\le5\times 10^5,w\le 10^{18}。

题解：对于若干种值线性组合相关问题，一般考虑同余最短路。具体来说，我们直接在模最小数 mn 意义下进行同余最短路，这样求出每个点的 dis_i 就代表 dis_i+k\cdot mn 都是可以拼出来的。但是，直接跑同余最短路一定是行不通的，复杂度无法低于 O(n^2)。（关于 O(n^2) 的此类同余最短路做法，详见魏老师的博客）考虑 Border 带给我们的特殊性质：可以划分为 \lceil\log_2{|S|}\rceil 个在值域上不交的等差数列。

考虑对于一个等差数列，应该如何跑同余最短路。设此等差数列为 \{x_i\}，其中 x_i=x_1+(i-1)d，项数为 L。那么，根据这一等差数列连出的边应该构成 \gcd(x_1,d) 个互不相关的子图，每个子图包含一个环（从某一个点 i 出发不断 +d 直到返回 i 途经的所有点）。对于每一个子图，其边形如从每个点出发，依次连向在环上排在其后的第 [1,L-1] 个点。同时，注意到环上最短路最小的结点一定不不会更新。因此，我们直接在这个位置断开。又由于子图形成区间更新的特性，直接使用单调队列维护其前面 [1,L-1] 个点中 dis_j-jd 最小的点即可。这样的单次复杂度就是 O(n) 的。

尝试将不同等差数列跑出的结果进行合并。注意到最大的问题在于模数会发生改变。设之前的模数为 pre，新的模数为 now。首先，我们先来分析一次同余最短路跑出的结果到底是什么意思。对于一个 dis_i，其含义为所有的 dis_i+k\cdot pre(k\ge 0) 都是可以被表示出来的。那么我们可以首先表示 dis_i 是可以表示出来的，然后再通过每个点 i 连向 i+pre 的方式来表示 dis_i+k\cdot pre 是可以被表示出来的。具体来说，首先先令dis_i 更新 dis’_{dis_i \ \bmod \ now}，然后再连边 i\rightarrow (i+pre)\bmod now，按照上面的方式更新即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e18;
char s[500005];
int nxt[500005];
int lg[1000005];
int dis[500005],tmp[500005];
vector<int>border[25];
void kmp(int n){
    for(int i=2;i<=n;i++){
        int p=nxt[i-1];
        while(p&&s[p+1]!=s[i]) p=nxt[p];
        if(s[p+1]==s[i]) p++;
        nxt[i]=p;
    }
    int x=nxt[n];
    while(x){
        border[lg[x]].push_back(n-x);
        x=nxt[x];
    }
    border[0].push_back(n);
}
int pos[500005];
int q[500005],ft=1,ed=0;
void upd(int bg,int x1,int d,int L,int m){
    int now=(bg+d)%m,mn=dis[bg],mnpos=bg;
    while(now!=bg){
        if(dis[now]<mn) mn=dis[now],mnpos=now;
        now=(now+d)%m;
    }
    int len=1;
    now=mnpos;
    pos[1]=now;
    now=(now+d)%m;
    while(now!=pos[1]){
        pos[++len]=now;
        now=(now+d)%m;
    }
    ft=1,ed=0;
    q[++ed]=1;
    for(int i=2;i<=len;i++){
        while(ed>=ft&&q[ft]<=i-L) ft++;
        if(ed>=ft) dis[pos[i]]=min(dis[pos[i]],dis[pos[q[ft]]]+d*(i-q[ft])+x1);
        while(ed>=ft&&dis[pos[i]]+i*d<=dis[pos[q[ed]]]+q[ed]*d) ed--;
        q[++ed]=i;
    }
}
void tyzdl(int x1,int d,int L,int p){
    int g=__gcd(p,d);
    for(int i=0;i<g;i++) upd(i,x1,d,L,p);
}
signed main(){
    lg[1]=0;
    for(int i=2;i<=1000000;i++) lg[i]=lg[i>>1]+1;
    int t,n,w;
    cin>>t;
    while(t--){
        cin>>n>>w;
        w-=n;
        scanf("%s",s+1);
        if(w<0){
            puts("0");
            continue;
        }
        for(int i=0;i<=20;i++) border[i].clear();
        for(int i=0;i<=n;i++) dis[i]=INF;
        dis[0]=0;
        kmp(n);
        int pre=-1;
        for(int i=0;i<=20;i++){
            if(border[i].size()){
                int now=border[i][0];
                if(pre!=-1){
                    for(int i=0;i<=n;i++) tmp[i]=INF;
                    for(int i=0;i<pre;i++){
                        int ok=dis[i]%now;
                        tmp[ok]=min(tmp[ok],dis[i]);
                    }
                    swap(tmp,dis);
                    tyzdl(0,pre,2,now);
                }
                pre=now;
                if(border[i].size()>1) tyzdl(border[i][0],border[i][1]-border[i][0],border[i].size(),now);
            }
        }
        int ans=0;
        for(int i=0;i<pre;i++) if(dis[i]<=w) ans+=(w-dis[i])/pre+1;
        printf("%lld\n",ans);
    }
    return 0;
}