Border 理论学习笔记
约定
-
字符串下标从 \(1\) 开始。
-
定义 \(S+T\) 为 \(S\) 与 \(T\) 这两个字符串的拼接。
-
定义 \(S[l:r]=S_l+S_{l+1}+\cdots +S_r\)。
-
定义 \(pre(i,S)=S[i:n],suf(i,S)=S[|S|-i+1:n]\)，也就是 \(S\) 的前后缀。
-
对于 \(S,T\)，若 \(T[i:i+|S|-1]\)，则称 \(i\) 是 \(S\) 在 \(T\) 中的匹配位置。
周期与 border
定义
若存在 \(p\)，使得 \(\forall 1\le i\le |S|-p,s_i=s_{i+p}\)，我们称 \(p\) 为 \(S\) 的周期。注意这里的周期并不一定能整除 \(|S|\)。例如，对于 \(\text{abbabbab}\)，我们也称 \(3\) 为其周期。
称 \(per(S)\) 为 \(S\) 的最小周期。
若存在 \(r\)，使得 \(pre(i,S)=suf(i,S)\)，则称 \(pre(i,S)\) 为 \(S\) 的 border。
也就是说，周期是一个长度，border 是一个字符串。
性质
- $pre(i,S) $ 是 \(S\) 的 border $\Leftrightarrow $ \(|S|-i\) 为 \(S\) 的周期。
证明：\(pre(i,S)=suf(i,S)\)，即 \(S[1:i]=S[|S|-i+1:n]\)，即 \(S_j=S_{j+|S|-i}\)。由周期定义得到 \(|S|-i\) 为 \(S\) 的周期。反过来也一样。
- Weak Periodicity Lemma：对于字符串 \(S\)，若 \(p,q\) 为 \(S\) 的周期，\(p+q\le |S|\)，那么 \(\gcd(p,q)\) 为 \(S\) 的周期。
证明：不妨设 \(p>q\)。
根据周期定义：
\(\forall i\le q,S_i=S_{i+p}=S_{i+p-q}\)。
\(\forall i>q,S_i=S_{i-q}=S_{i+p-q}\)。
因此，\(\forall 1\le i\le |S|-(p-q),S_i=S_{i+p-q}\)。因此 \(p-q\) 为 \(S\) 的周期。
根据更相减损法的过程，显然 \(\gcd(p,q)\) 也为 \(S\) 的周期。
- Periodicity Lemma：对于字符串 \(S\)，若 \(p,q\) 为 \(S\) 的周期，\(p+q\le |S|+\gcd(p,q)\)，那么 \(\gcd(p,q)\) 为 \(S\) 的周期。
不会证捏。
- 对于字符串 \(S,T\) ，若 \(2|S|\ge |T|\)，则 \(S\) 在 \(T\) 中的所有匹配位置构成等差序列。
证明：在匹配位置个数小于 \(3\) 时显然成立。
在匹配位置个数大于等于 \(3\) 时，我们考虑第一个，第二个和另外任意一个匹配串：
图中红色部分均为 \(P_1\) 的 border。可以得出蓝色部分是 \(P_1\) 的一个周期。
我们设 \(P_1,P_2\) 间隔为 \(d\)，\(P_2,P_t\) 间隔为 \(f\)。
那么 \(r=\gcd(d,f)\) 为 \(P_1\) 的周期。我们设 \(per(P_1)=p\le r\)。
假设橙色部分为 \(pre(|S|-p,S)\)，若 \(p<d\)，发现从第二条橙色位置（即 \(P_1\) 右移 \(p\) 位）开始又能形成一个匹配。可以结合图像理解，因为 \(P_2\) 的前缀与 \(P_1\) 相同，第二三条橙色拼到一起恰好能形成匹配。
那么，因为 \(P_2\) 是第二个匹配位置，这产生了矛盾。因此，\(p=d\)，\(r\ge d\) 且 \(r=\gcd(d,f)\le d\)，得 \(r=d\)。那么 \(d|f\)，也就是说，对于任何 \(t\ge 3\)，\(P_2,P_t\) 的间隔是 $d $ 的倍数。同时，类似于上一段的分析，间隔 $d $ 的倍数处又能形成匹配，因此 \(S\) 在 \(T\) 中的所有匹配位置构成等差序列。
border 的结构
- 若 \(pre(i,S)\) 是 \(S\) 的 border，\(pre(j,S)(j<i)\) 是 \(pre(i,S)\) 的 border。
border 的 border 是 border。比较显然，就不证了。
- \(S\) 的长度不小于 \(\dfrac{|S|}{2}\) 的 border 长度构成一个等差序列。
证明：设 \(n-p\) 为 \(S\) 的最长 border，\(n-q\) 也为 \(S\) 的 border。（\(p,q\ge \frac{|S|}{2}\)）
那么 \(p,q\) 为 \(S\) 的周期，由 Weak Periodicity Lemma 有 \(\gcd(p,q)\) 为 \(S\) 的周期。
由于 \(n-p\) 是最长 border，\(p\le \gcd(p,q)\)，得 \(p=\gcd(p,q)\) 即 \(p|q\)。
有了整除就和上上个性质很像了。通过与上面类似的分析可以得出该结论。
- 推论：\(S\) 的所有 border 长度可以组成 \(O(\log |S|)\) 个等差数列。
证明：将 \(S\) 所有 border 按照长度分为 \([1,2),[2,4),[4,8)\cdots [2^{i-1},2^i),[2^i,S)\) 这 \(O(\log |S|)\) 类。
我们以每一组中的最长 border 作为基准，那么根据上面的定理，这一组中所有 border 的长度构成等差序列。那么总共就是 \(O(\log |S|)\) 个等差序列。
子串周期查询
问题：一个长度为 \(n\) 的字符串 \(S\)，每次询问一个子串 \(T\) 的所有周期，用 \(O(\log |T|)\) 个等差序列表示。
问周期等价于问 border。
我们首先将 border 按照长度分类：
- \(x\in[2^i,2^{i+1})\)。
- \(x\in[2^k,|T|)\)。
首先，我们先解决第一种情况。
如图，对于 border \(u\)，\(pre(2^i,T)\) 是 \(u\) 的前缀，\(suf(2^i,T)\) 是 \(u\) 的后缀。
因此，我们找出所有 \(suf(2^i,T)\) 在 \(pre(2^{i+1},T)\) 中的匹配位置（这里的匹配位置指的是 \(suf(2^i,T)\) 的串首字符对应位置）和所有 \(pre(2^i,T)\) 在 \(suf(2^{i+1},T)\) 中的匹配位置（这里的匹配位置指的是 \(pre(2^i,T)\) 的串末字符对应位置），并计算两边匹配位置到 \(T\) 两端的长度（图中红色位置），发现如果\(u\) 是 \(T\) 的 border，那么两端红色位置的长度是相同的。
那么，我们求出所有 \(suf(2^i,T)\) 在 \(pre(2^{i+1},T)\) 中的匹配位置和所有 \(pre(2^i,T)\) 在 \(suf(2^{i+1},T)\) 中的匹配位置，再翻折，合并就能得到这一段的答案。
考虑情况二，发现本质相同，就是将上面的 \(2^i\gets 2^k,2^{i+1}\gets |T|\)。
因此，我们现在要解决的问题形如：
- 求出 \(suf/pre(2^i,S)\) 在 \(pre(len,S)\) 中的匹配位置。
- 合并两个等差数列。
我们先考虑问题 1。发现我们要匹配的字符串长度形如 \(2^i\)。考虑倍增 SA 的过程，如果我们在过程中将字符串的 \(rk\) 记录下来，那么对于所有长度为 \(2^i\) 的字符串，它们在第 \(i\) 轮的 \(rk\) 是相同的。我们按照下标顺序，将每一轮中 \(rk\) 相同的字符串的下标插入 vector 中，那么查询某个区间中的匹配位置直接二分查找即可。具体地，由于匹配位置是一个等差序列，我们只需查找第一二个和最后一个匹配位置即可。复杂度是 \(O(\log^2 n)\) 的，因为我们要做 \(O(\log n)\) 轮二分。
问题二中合并两个等差序列是好解决的，可以通过一些解同余方程之类的东西做到 \(O(\log^2 n)\)。
到这里，我们就能用 \(O(n\log n)-O(\log^2n)\) 的复杂度解决这个问题了。
能不能更给力？发现瓶颈就是上面的两个问题，考虑优化。
首先对第一个问题进行优化。实际上，我们只在乎形如 \([x,x+2^i-1]\) 的段的匹配信息。这样的段一共只有 \(O(n)\) 个，考虑通过一些手段快速求出这些段的匹配信息。
发现长为 \(2^i\) 的字符串只有 \(O(n)\) 个，而 \(i\) 的取值只有 \(O(\log n)\) 种，那么匹配信息的空间复杂度是 \(O(n\log n)\) 的，可以用哈希表全部存下。具体地，对于这 \(O(n)\) 个段，我们都开一个哈希表来维护信息，对每一个哈希值，我们维护该值对应字符串在区间中第一次/第二次/最后一次出现的位置即可 \(O(1)\) 查询。哈希值 \(h_{i,i+2^j-1}\) 可以通过 \(h_{i,i+2^{j-1}-1}\) 和 \(h_{i+2^{j-1},i+2^j-1}\) \(O(1)\) 合并，因此预处理的复杂度是 \(O(n\log n)\) 的。
上面的方法要求匹配区间的长度也是 \(2^i\)，可能在做 \([2^k,|T|)\) 的时候不适用，这一段要暴力求。这样，我们就将第一部分的单次询问复杂度优化到了 \(O(\log n)\)。
然后考虑第二个问题。事实上，我们有下面的性质：
- 对于四个字符串满足 \(|x_1|=|y_1|\ge |x_2|=|y_2|\)，\(x_1\) 在 \(y_2+y_1\) 中至少匹配 \(3\) 次，\(y_1\) 在 \(x_1+x_2\) 中至少匹配 \(3\) 次，那么 \(x_1\) 与 \(y_1\) 最小周期相等。
证明：若上述性质不成立，不妨设 \(per(x_1)>per(y_1)\)，考虑 \(x_1\) 在 \(y_1+y_2\) 中的最后一次匹配，设其与 \(y_1\) 的重叠部分为 \(z\)，则 \(|z|>2per(x_1)>per(x_1)+per(y_1)\)，则 \(z\) 有周期 \(d=\gcd(per(x_1),per(y_1))\)，那么 \(d|per(x_1)\) 且 \(d<per(x_1)\)，那么 \(d\) 为 \(x_1\) 周期且 \(d<per(x_1)\)，矛盾。
于是，我们的两个等差序列要么其中一个项数小于 \(3\)，要么公差相同，显然可以 \(O(1)\) 合并。
至此，我们以 \(O(n\log n)-O(\log n)\) 的复杂度解决了这个问题。
有一道题 [BJWC2018] Border 的四种求法 是求最长 border，可以用来测试上面的问题。
给出 \(O(\log^2n)\) 的实现：
#include<bits/stdc++.h>
using namespace std;
char s[1000010];
int Q,l,r,n,m,cnt;
int ans,bu[1000010],k1[20][200010],p[1000010],sa[1000010];
vector<int> pos[20][200010];
struct Seq{
int st,ed,sum,delta;
}none;
bool In(Seq x,int y){
return !((y-x.st)%x.delta);
}
Seq Merge(Seq x,Seq y){
if(x.delta==y.delta){
if(x.st>y.st) swap(x,y);
if(x.ed<y.st) return {0,0,0,0};
x.st=y.st;x.ed=min(x.ed,y.ed);x.sum=(x.ed-x.st)/x.delta+1;
return x;
}
if(x.sum<y.sum) swap(x,y);
int cnt=0,a[10]={},z=y.st;
for(int i=1;i<=y.sum;i++){
if(In(x,z)) a[++cnt]=z;
z+=y.delta;
}
if(!cnt) return {0,0,0,0};
x.st=a[1],x.ed=a[cnt],x.sum=cnt;
if(cnt>1) x.delta=(x.ed-x.st)/(cnt-1);
else x.delta=0;return x;
}
int fndl(int a,int b,int x){
int l=0,r=pos[a][b].size()-1;
if(r<0||pos[a][b][r]<x) return -1;
while(l<r){
int mid=(l+r)>>1;
if(pos[a][b][mid]<x) l=mid+1;
else r=mid;
}
return l;
}
int fndr(int a,int b,int x){
int l=0,r=pos[a][b].size()-1;
if(r<0||pos[a][b][0]>x) return -1;
while(l<r){
int mid=(l+r+1)>>1;
if(pos[a][b][mid]<=x) l=mid;
else r=mid-1;
}
return l;
}
int workans(int k,int l1,int r1,int l2,int r2){
int L=(1<<k),ps1=k1[k][l1],ps2=k1[k][r2-L+1];
int f1=fndl(k,ps1,l2);
int f3=fndl(k,ps2,l1);
if(f1==-1||f3==-1) return 0;
int f2=fndr(k,ps1,r2-L+1);
int f4=fndr(k,ps2,r1+1-L);
if(f2==-1||f4==-1||f1>f2||f3>f4) return 0;
Seq x,y;
if(f1==f2) x.st=x.ed=pos[k][ps1][f1],x.delta=1,x.sum=1;
else{
x.st=pos[k][ps1][f1],x.ed=pos[k][ps1][f2],
x.delta=pos[k][ps1][f1+1]-x.st,x.sum=(x.ed-x.st)/x.delta+1;
}
if(f3==f4) y.st=y.ed=pos[k][ps2][f3],y.delta=1,y.sum=1;
else{
y.st=pos[k][ps2][f3],y.ed=pos[k][ps2][f4],
y.delta=pos[k][ps2][f3+1]-y.st,y.sum=(y.ed-y.st)/y.delta+1;
}
Seq z=y;y.st=(l1+r2-z.ed-L+1),y.ed=(l1+r2-z.st-L+1);
x=Merge(x,y);
if(x.sum) return r2-x.st+1;
return 0;
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1),m=26;
for(int i=1;i<=n;i++) ++bu[s[i]-'a'+1],k1[0][i]=s[i]-'a'+1;
for(int i=1;i<=m;i++) bu[i]+=bu[i-1];
for(int i=1;i<=n;i++) sa[bu[s[i]-'a'+1]]=i,--bu[s[i]-'a'+1];
for(int i=1;i<=n;i++) pos[0][k1[0][i]].push_back(i);
for(int k=1;k<=n;k<<=1){
int lgk=__lg(k)+1;
cnt=0;
for(int i=n-k+1;i<=n;i++) p[++cnt]=i;
for(int i=1;i<=n;i++){
if(sa[i]>k) p[++cnt]=sa[i]-k;
}
memset(bu,0,sizeof(bu));
for(int i=1;i<=n;i++) ++bu[k1[lgk-1][i]];
for(int i=1;i<=m;i++) bu[i]+=bu[i-1];
for(int i=n;i>=1;i--) sa[bu[k1[lgk-1][p[i]]]]=p[i],--bu[k1[lgk-1][p[i]]];
k1[lgk][sa[1]]=1,m=1;
for(int i=2;i<=n;i++){
if(k1[lgk-1][sa[i]]==k1[lgk-1][sa[i-1]]&&k1[lgk-1][sa[i]+k]==k1[lgk-1][sa[i-1]+k]) k1[lgk][sa[i]]=m;
else k1[lgk][sa[i]]=++m;
}
for(int i=1;i<=n;i++) pos[lgk][k1[lgk][i]].push_back(i);
}
scanf("%d",&Q);
for(int i=1;i<=Q;++i){
scanf("%d%d",&l,&r);ans=0;
for(int k=__lg(r-l)+1;k;--k){
ans=workans(k-1,l,min(l+(1<<k)-1,r-1),max(l+1,r-(1<<k)+1),r);
if(ans){
printf("%d\n",ans);
break;
}
}
if(ans==0) printf("%d\n",ans);
}
return 0;
}