字符串相关

发表于 2021-10-17 更新于 2021-11-08

这个页面主要放一些关于字符串的结论（猜想）。

有些猜想不知道能不能拿来出题。

记号

符号

$|s|$：$s$ 的长度。
$\Sigma$：字符集。
$\epsilon$：空串/空字符。
$s^k$：$s$ 复制 $k$ 遍。
$s^R$：$s$ 翻转。
$s_i$：$s$ 的第 $i$ 个字符（下标从 $1$ 开始）
$\sqrt[k]{s}$：$t=\sqrt[k]{s}\Longleftrightarrow s=t^k$。

集合

$\text{per}(s)$：$s$ 的最小周期。$\text{Per}(s)$：$s$ 所有周期组成集合。
$\text{Pre}(s)/\text{Suf}(s)$：$s$ 前缀/后缀集合。
$\text{Sub}(s)$：$s$ 所有子串的集合。
$\text{Cir}(s)$：$s$ 所有循环同构串集合。
$\text{Runs}(s)$：$s$ 所有 $\text{Runs}$ 集合。
$\text{Lyn}$：所有 Lyndon Word 集合。
$\text{Pal}$：所有回文串集合。
$\text{Pow}^k$：所有 $k$ 次方串集合。
以上所有集合都是字符串集合。
$\text{Len}(S)$ 表示字符串集合 $S$ 所有字符串总长度。
$\text{Min}(S)$ 表示字符串集合 $S$ 中字典序最小的串，$\text{Max}(S)$ 同理。

简写

$\text{Pow}$ 表示所有 $k\in \mathbb Z,k\geq 2$，$\text{Pow}^k$ 的并。
$\text{suf}_i(s)$：$s$ 从 $i$ 开始的后缀。$\text{pre}_i(s)$ 同理。
若 $x\in \mathbb{Z}$，则 $x\in \text{Per}(s)$ 等价于 $s[:x]\in\text{Per}(s)$，$\text{Pal}$ 等同理。
$\text{PalPre}(s)$ 等价于 $\text{Pal}\cap\text{Pre}(s)$，其余同理。
$\text{MinPre}(s)$ 表示最长前缀，其余同理。

经典结论

若 $p,q\in\text{Per}(s)$，且 $p+q-\gcd(p,q)\leq |s|$，则 $\gcd(p,q)\in\text{Per}(s)$。
$\text{Sub}(s)$ 中本原平方串个数为 $O(|s|\log |s|)$。
$\text{Runs}(s)$ 的所有指数之和为 $O(n)$。
$s$ 的所有 border 可以被分为 $\log n$ 个等差数列。

已经证明的结论

关于回文串

结论

若 $s\in \text{PalPow}^k$，则 $\sqrt[k]s\in\text{Pal}$。

证明

令 $t=\sqrt[k]s$。

若 $k$ 为奇数有 $t=t^R$，若 $k$ 为偶数则有 $t^2\in\text{Pal}$ 都可以推出 $t\in\text{Pal}$。
若 $p,q\in\text{PrePal}(s)$ 且 $p< q,2p>q$，则 $2p-q\in\text{PrePal}(s)$。

证明

$\forall x\in[1,2p-q],\ s_x=s_{p-x}=s_{q-p+x}$，那么 $s[p+1:q]$ 是一个回文串。

那么 $s[1:2p-q]$ 也是一个回文串。
若 $s\not\in \text{Pow}$，$\text{Cir}(s)$ 中至多有 $2$ 个串是回文串。

证明

一种方法当然是暴力推，但事实上有些困难。

有一种很巧妙的方法：将 $s$ 看做是一个定义在圆上的离散函数。那么循环串为回文串等价于该函数的对称轴。

有两条不同对称轴的函数一定为周期函数，无论其是否为离散函数。

故 $s$ 至多只有两条重合的对称轴。
删去 $\text{PalPre}(s)$ 前 $\sqrt n$ 与后 $\sqrt n$ 个后剩下所有元素构成一个等差数列。

证明

考虑假设删去前 $B$ 个元素与后 $B$ 个元素，最优构造一定是构造 $B+2$ 个 $\texttt{a}$ 然后构造一个 $\texttt{b}$，最后再复制 $B$ 遍。

可以发现这种构造下至少要 $B^2$ 的字符串。
树上本质不同回文串个数是 $O(n\sqrt n)$ 的。

证明

完整证明见论文

简要证明咕咕咕了。

关于 Runs/Lyndon串/平方串

结论

$s+w,w+t\in\text{Lyn}\Longrightarrow s+w+t\in\text{Lyn}$。

证明

易得 $\text{MinSuf}(s+w+t)=\text{Min}\left(\text{Suf}(s+w)+t)\cup(\text{Suf}(s)+w+t)\right)$。

根据定义有 $s+w\leq\text{MinSuf}(s+w)$。同样有 $w+t\leq\text{MinSuf}(w+t)<\text{Minsuf}(t)$。

故 $s+w+t\leq\text{MinSuf}(s+w+t)$，$s+w+t\in\text{Lyn}$。
$\text{Len}(\text{Runs}(s))=O(n\log n)$。
证明

根据 $\text{Runs}$ 的理论，任意两个 Lyndon Root 不交。

所以容易发现对于串 $s$ 用如下方式递归构造：
- 假设长度为 $l$ 的串总长度为 $F(l)$。
- 找到最长的 Lyndon Root $t$ 对应的 Runs，将序列划分成若干段。
- 假设该 $\text{Runs}$ 指数为 $k$，那么总长度为 $tk$，剩下若干段长度为 $kF(t)+F(n-kt)$，故 $F(n)=kF(t)+F(n-kt),k\geq 2$。
可以证明当 $k=2$ 时取最长为 $O(n\log n)$。
$\text{Len}(\text{Pow}^2\text{Sub}(s))=O(|s|)$。

证明

考虑用类似于 $6$ 的方法证明。

一个 $\text{Run}$ $(l,r,p)$ 中至多只有 $\lfloor\frac{r-l+1}{p}\rfloor$ 个平方串，故 $\text{Pow}^2$ 串总长度不超过 $\text{Run}$ 总长度。

而一个 $\text{Runs}$ 递归构造时有所有段全等，故 $F(n)=F(t)+F(n-kt)+O(k),k\geq 2$。总长度为 $O(|s|)$。
$\text{Len}(\text{PowSub}(s))=O(|s|)$。

证明
看起来比定理 [$3$] 高级？其实不过把递推式换成了 $F(n)=F(t)+F(n-kt)+O(kt),k\geq 2$。
其实是一样的。。。

推论

定义 Run $(l,r,p)$ 与 $(l’,r’,p’)$ 本质相同当且仅当 $r-l=r’-l’,s[l:r]=s[l’:r’]$。

则 $\text{Len}(\text{Runs}(s))=O(|s|)$。

看起来很牛逼，但貌似没有什么用。