字符串 | DDOSvoid's Blog

简介

其实是来讲几个规定的

$|S|=n$ 表示串 $S$ 的长度，$\sigma=|\sum|$ 表示字符集大小

$S[i\cdots j]$ 表示由串 $S$ 的第 $i$ 到第 $j$ 个字符形成的字符串

$Sc$ 表示在串 $S$ 后加一个字符 $c$ 得到的字符串

$Sw$ 表示在串 $S$ 后加一个字符串 $w$ 得到的字符串

$pre(S,i)$ 表示前缀 $S[1\cdots i]$，$suf(S,i)$ 表示后缀 $S[i\cdots n]$

$S[i_1\cdots j_1]$ 和 $S[i_2\cdots j_2]$ 本质不同表示他们对应的字符串不同，即 $S[i_1\cdots j_1]\neq S[i_2\cdots j_2]$

$len(S)$ 表示串 $S$ 的长度，$rev(S)$ 表示将串 $S$ 翻转之后得到的串

$per(S)$ 表示 $S$ 的最小周期

实际上就是字符串 $s$ 的某个前缀如果也是后缀的话，那么这个前缀就是一个 $border$

实际上 $kmp$ 的 $nxt$ 数组求得就是 $S[1…i]$ 的最长的 $border$

若 $0 < p\le len(S),S[i]=S[i+p],1\le i \le len(S)-p$，就称 $p$ 为 $S$ 的周期，记最小周期为 $per(S)$

注意到 $len(S)-nxt[len(S)]$ 如果整除 $len(S)$，则 $len(S)-nxt[len(S)]$ 为 $S$ 的最小真周期

如果不整除的话，则表示 $S$ 由若干个 $S[1\cdots len(S)-nxt[len(S)]]$ 加上一个 $S[1\cdots len(S)-nxt[len(S)]]$ 的前缀组成

这个时候我们称 $len(S)-nxt[len(S)]$ 为 $S$ 的最小假周期

需要注意，假周期和真周期都属于周期

$p$ 和 $q$ 是 $S$ 的周期，$p+q\le len(S)$，则 $(p,q)$ 也是 $S$ 的周期

证明：不妨设 $p<q$，记 $d=q-p$

由于 $p+q\le len(S)$，所以对于所有 $i\in[1,len(S)-d]$，一定有 $i-p\ge 1\vee i+q\le len(S)$

若 $i-p\ge 1$，则有 $S[i]=S[i-p]S[i-p+q]=S[i+d]$

若 $i+q\le len(S)$，则有 $S[i]=S[i+q]=S[i+q-p]=S[i+d]$

则 $d$ 是 $S$ 的周期，能够发现这是一个辗转相减的过程，最终能够得到 $(p,q)$ 也是 $S$ 的周期

$p$ 和 $q$ 是 $S$ 的周期，$p+q-(p,q)\le len(S)$，则 $(p,q)$ 也是 $S$ 的周期

引理1：字符串 $u$，$v$ 满足 $2\times len(u)\ge len(v)$，则 $u$ 在 $v$ 中的所有匹配位置构成一个等差数列

引理2：若这个等差数列有至少三项，则其公差 $d$ 等于 $u$ 的最小周期 $per(u)$，易得 $per(u)\le \frac{len(u)}{2}$