一些字符串的定理

Part 1 Border,Period 理论

设有一长 nn 的字符串 SS

1.1 定义

  • Border:

    满足 1k<n1\le k<nS[1,k]=S[nk+1,n]S_{[1,k]}=S_{[n-k+1,n]}kk

    不妨把 SS 的 Border 放入集合 B(S)B(S) 中。

    Bl(S)B_l(S)max{kkB(S)}\max\{k|k\in B(S)\}

  • Period(周期元):

    满足 1k<n1\le k<n1ink\forall 1\le i\le n-k 都有 Si=Si+kS_i=S_{i+k}kk

    不妨把 SS 的 Period 放入集合 P(S)P(S) 中。

1.2 基本性质&定理

1.2.1 对偶性

kB(S)nkP(S)k\in B(S)\Leftrightarrow n-k\in P(S)

证明考虑把已知的等价关系画出来。

1.2.2 弱周期定理

x,yP(S),x+yngcd(x,y)P(S)x,y\in P(S),x+y\le n\Rightarrow \gcd(x,y)\in P(S)

证明

不妨令 x<yx<y

仅需证明 yxP(S)y-x\in P(S),辗转相除会出手。

对于 SiS_i

  • ixi\le xi+yni+y\le nSi=Si+y=Si+yxS_i=S_{i+y}=S_{i+y-x}
  • i>xi>xSi=Six=Si+yxS_i=S_{i-x}=S_{i+y-x}

1.2.3 Border 的传递性

yB(S[1,k]kB(S))yB(S)y\in B(S_{[1,k]}|k\in B(S))\Rightarrow y\in B(S)

即 Border 的 Border 还是 Border。

证明考虑画画。

1.2.4 Border 的区间包含单调性

Bl(S[l+1,r1])Bl(S[l,r])+2B_l(S_{[l+1,r-1]})\ge B_l(S_{[l,r]})+2

1.3 Border 的结构

1.3.1 Border 的树状结构

B(S)=B(S[1,Bl(S)])+{Bl(S)}B(S)=B(S_{[1,B_l(S)]})+\{B_l(S)\}

证明

根据传递性,有 B(S[1,Bl(S)])B(S)B(S_{[1,B_l(S)]}) \subset B(S)

由于 Bl(S)B_l(S)SS 最长的 Border,所以 B(S)B(S[1,Bl(S)])={Bl(S)}B(S)-B(S_{[1,B_l(S)]})=\{B_l(S)\}

这启发我们可以建出 nn 个点的树,每个点代表 SS 的一个前缀,ii 的父亲为 Bl(S[1,i])B_l(S_{[1,i]})

容易发现这棵树的根为 11,每个节点的 BB 集合就是它到根路径上的节点集合。

实际上这就是 AC 自动机的 fail 树。

1.3.2 Border 的等差数列结构

1.3.2.1 引理

所有满足 2kn2k\ge n 的 Border kk 构成一个等差数列

证明

考虑 P(S)P(S)n2\le \lfloor\frac{n}{2}\rfloor 的元素 xx 构成的集合 Ps(S)P_s(S),根据弱周期定理,显然 r=min{Ps(S)}r=\min\{P_s(S)\}Ps(S)P_s(S) 中所有元素的因子。

且由于 rr 是最小的 Period,Ps(S)P_s(S) 一定为 {kr1k,krn2}\{kr|1\le k,kr\le \lfloor\frac{n}{2}\rfloor\}rr 的正整数倍构成的集合。

根据对偶定理,A={nkr1k,krn2}B(S)A=\{n-kr|1\le k,kr\le \lfloor\frac{n}{2}\rfloor\}\subseteq B(S),并且 AA 包含所有 2kn2k\ge n 的 Border kk

也就是说,满足 2kn2k\ge n 的 Border kk 构成了一个首项为 nrn-r,公差为 r-r 的等差数列。

1.3.2.2 定理 - 等差数列结构

B(S)B(S) 构成 O(logn)O(\log n) 个等差数列

证明

根据引理 1.3.2.1,所有满足 2kn2k\ge n 的 Border kk 构成了一个等差数列。

l=max{kkB(S),2k<n}l=\max\{k|k\in B(S),2k<n\},类比 1.3.1(树状结构)的证明,易知去除该等差数列后剩下的 Border 集合为 B(S[1,l])+{l}B(S_{[1,l]})+\{l\}

那么在 S[1,l]S_{[1,l]} 上调用一次引理 1.3.2.1,可以实现继续砍半。

由于每次砍半,所以总共会得到 O(logn)O(\log n) 个等差数列。

等差数列的寻找方法

这里给出一种寻找等差数列的方法:(该方法把 nn 也当作 SS 的 Border)

  • 找到 SS 的极长 Border kk,设 l=n(nk)nn2nkl=n-(n-k)\lceil\frac{n-\lfloor\frac{n}{2}\rfloor}{n-k}\rceil
  • 加入新的首项为 n(nk)nn2nkn-(n-k)\lceil\frac{n-\lfloor\frac{n}{2}\rfloor}{n-k}\rceil,末项为 nn,公差为 nkn-k 的等差数列;
  • 找到 S[1,l]S_{[1,l]} 的最长 Border pp,递归处理 S[1,p]S_{[1,p]}

1.4 例题