建议看到结论之后直接画图自己推
目前定义 \(s[l,r]\) 为字符串 \(s\) 的 \([l,r]\)，定义 \(nxt_i\) 为 KMP 算法所得。
定义： \(s[1,i]=s[n-i+1,n]\)，则称 \(s[1,i]\) 是 \(s\) 的一个 border
可能证明会比较浅显，但仅供笔者理解。
nxt树定义：连边 \(nxt_i\to i\) 的一棵树。
- 周期性
周期定义：对于 \(s[1,n]\)，一个周期 \(t\) 等价于满足 \(\forall i,i+t\in [1,n],s[i]=s[i+t]\)
因此有 \(s[1,i]\) 为一个 border 等价于存在一个周期 \(t=n-i\)Kmp的 \(nxt_i\) 表示 \(s[1,nxt_i]=s[i-nxt_i+1,i]\)，是一个前缀的最大 \(border\)。
- 总和性
对于 \(s[1,n]\) 的所有 \(border\) 长度由以下代码给出：
int t=nxt[n];vector<int>border;while(t)border.push_back(t),t=nxt[t]
这等价于 nxt 树上 \(n\) 的所有祖先。证明仅需考虑假设一个 \(nxt_{nxt_i}<k<nxt_i\)，那么可以推出 \(k=nxt_{nxt_i}\) 即可。
应用：\(s[1,i]\) 在 \(s[1,k]\) 的出现次数，等价于 nxt 树上的点 \(i\) 的子树中所有 \(\le k\) 的节点个数。
变形：在 \(t[1,m]\) 中，\(s[1,n]\) 的出现次数。构造 \(G=s+?+t\) 即可。
- 匹配性：
对于 \(j<k\) 为两个 border。
那么对于原串 \(s\)，任意一个位置满足 \(s[pos-k+1,pos]=s[1,k]\)，就有 \(s[pos-j+1,pos]=s[1,j]\)
证明：因为 \(j<k\)，所以 \(s[1,j]=s[k-j+1,k]\)，后续自证不难。
同时在 nxt 树上的视角，\(j\) 是 \(k\) 的祖先，且 \(pos\) 属于子树 \(k\)。自然属于子树 \(j\)。
- 最小表示可行性
对于一个字符串 \(s[1,n]\)，若 \(p\) 为这个字符串循环最小表示的开头位置，一个必要条件是：
存在一个字符串 \(t\)，满足 \(s[p,n]+t\) 是 \(s[1,n]+t,s[2,n]+t,\dots s[n,n]+t\) 最小值。证明：这等价于对于后缀 \(s[k,n],k<p\)，需要满足 \(s[p,n]<s[k,k+n-p]\)，对于后缀 \(s[k,n],k>p\)，需要满足 \(s[p,p+n-k]<s[k,n]\)
- 最小后缀相关
记后缀 \(suf_i=s[i,n]\)。
记最小后缀为 \(minsuf\)
设集合 \(P\) 为在所有后缀后追加一个字符串 \(t\)，可能成为最小后缀的后缀。更详细地，这个可能成为最小后缀的后缀 \(suf_k\)，满足对于 \(t<k\)，\(s[t,t+n-k]<s[k,n]\)，对于 \(t>k\)，\(s[t,n]>s[k,k+n-t]\)
性质：
\(P\) 中串互为前缀（因为仅凭当前信息无法判断大小，所以长度较小串是长度较大串的前缀），同时长度较小串也是长度较大串的后缀，所以是 border 关系
\(\forall S,T\in P,|S|>|T|\)，有 \(|S|>2|T|\)。
证明：
若 \(|T|<|S|\le 2|T|\)，则显然有存在串 \(AB\)，有 \(S=AB,T=AAB\)
其中 \(A\) 可空。
考虑往后加入一个串 \(U\) 进行比较，则 \(ABU,AABU\) 相当于比较 \(BU,ABU\)
- 若 \(BU<ABU\)，则可以推出 \(A\) 非空，且有后缀 \(B\) 优于 \(AB\) 也就是 \(S\)，所以 \(S\) 并不是最小后缀，矛盾
应用：「JSOI2019」节日庆典
\(|P|\le \log n\)。
- 弱周期定理
若 \(p,q,p>q\) 为 \(s[1,n]\) 的周期，\(p+q\le n\)，那么 \(p-q\) 也是 \(s[1,n]\) 的周期。
推论：更相减损术得 \(\gcd(p,q)\) 是 \(s[1,n]\) 的周期。
证明：\(s_i=s_{i+p}=s_{i+q}\implies s_i=s_{i+p-q}\)
- 周期定理
若 \(p,q\) 为 \(s[1,n]\) 周期，\(p+q-\gcd(p,q)\le n\)，则 \(\gcd(p,q)\) 为 \(s[1,n]\) 周期。
证明类同。
- 前缀周期定理
若 \(s[1,i]\) 有周期 \(d\)，\(s[1,n]\) 有周期 \(a\)，若 \(d|a,i\ge a\)，则 \(s[1,n]\) 也有周期 \(d\)。
证明很简单，考虑 \(s[1,a]\) 由若干个 \(s[1,b]\) 重复组成。
- 等差数列定理 - version 1
对于 \(2|S|\ge |T|\)，串 \(S\) 在串 \(T\) 中的匹配位置为等差数列。
设匹配位置为 \(b_1\sim b_m\)。
我们考虑只保留串 \(T\) 的 \([b_1-|S|+1,|b_m|]\) 部分，则简化为了一个 \(S\) 为 \(T\) 的border的问题。
这样的话，我们不妨令这个新的串代替 \(T\)，下面表述以新串为主。
可以知道由于 \(2|S|>|T|\)，所以这些匹配位置所代表的区间有交。
那么对于 \(i,j\)，\(T[b_i-|S|+1,b_i]=T[b_j-|S|+1,b_j]\)，因此 \(b_j-b_i\) 就成为了一个周期，且完全覆盖。
根据弱周期定理，可以得到匹配位置是一个等差数列。另一种想法：考虑两个周期 \(p,q,p<q\)，可知 \(q=kp\)。因此这些个匹配位置之差都是一个周期，进而都是周期。
- 9.的重要推论：
考虑两个串 \(S,T\),定义集合 \(G=\lbrace k_1\sim k_n\rbrace,k\ge |S|/2,S[1,k]=T[n-k+1,n]\)。
那么这也是个等差数列。
证明很简单，取出最大的 \(k\)，然后很明显剩下的全是 \(S[1,k]\) 的border。
- 等差数列定理 - version 2
一个串的 \(border\) 按长度排序后，可以划分为 \(O(\log n)\) 个等差序列，也即周期同样可以。
反复运用 10.将字符串划分为 \([2^{i-1},2^i-1]\) 若干段，这样可以遍历完所有的border。按照这样分组后每组贡献一条 border 等差数列链。
- 设 \([1,i]\) 的所有 border 长度为 \(S(i)\)，则 \(x\in S(i),x\neq 1\implies x-1\in S(i-1)\)
这个感觉挺显然的，因为 若 \([1,x]=[i-x+1,i]\)，则 \([1,x-1]=[(i-1)-(x-1)+1,i-1]=[i-x+1,i-1]\)
-
延续 12. 的定义，则有 \(S(nxt_i)\subseteq S(i)\)，且差的那一部分恰可以从 \(S(i-1)\) 里 \(\ge nxt_i\) 的那部分元素补上来
应用：QOJ 9372