【闲话 No.6】 Lyndon 串与 runs 相关
约定有些约定可能并没有被广泛认可，但是为了行文需要还是写在这里，请您理解。
在下文中，如无特殊说明，我们用 \(n\) 表示问题规模大小，比如任何字符串的大小。所有数组下标从 \(1\) 开始。
我们定义对于一个字符串 \(s\)，\(s_i\) 表示 \(s\) 的第 \(i\) 个字符，\(s_{i,j}\) 表示这个串在 \(\) 区间内的子串，\(\operatorname{pre}_s(i)\) 表示这个串以 \(i\) 结尾的前缀，即 \(s_{1,i}\)，\(\operatorname{suf}_s(i)\) 表示这个串以 \(i\) 为开头的后缀，即 \(s_{i,n}\)。
如无特殊说明，文中所有对字符或字符串定义的“大于”“小于”均基于大家所熟知的字典序。我们定义空字符是字典序最小的字符，且所有字符串的两边都有无数个空字符，所有串内都没有空字符。在进行字符串拼接等边界情况并不重要的操作时，我们默认忽略这些空字符。
我们定义两个字符串的乘法 \(st\) 表示将 \(s\) 与 \(t\) 首尾相接得到的字符串，注意不同于数的乘法，字符串乘法不满足交换律。定义字符串的幂 \(s^k\) 表示将 \(k\) 个 \(s\) 依次首尾相接得到的字符串。
我们定义关键点为两个字符串在比较时对结果贡献的位置，比如判定 \(ab < ac\)，关键点为第二个位置。若关键点为空字符，则称这两个字符串的比较产生了一次关键溢出，可以发现，如果在一次比较之中长串较小，短串较大，则不可能发生关键溢出，同时也说明了 Lyndon 串与它的所有后缀比较都不会溢出。由于下文可能经常使用这个结论，我们称之为结论零。由于关键点产生导致接下来的位置无需比较，我们成这种现象为短路。
Lyndon 串 与 Lyndon 分解
我们定义一个字符串为 Lyndon 串，当且仅当对于该字符串的所有后缀，该字符串本身是最小的一个。由于字符串的后缀长度互不相同，故不存在相等的后缀，因此 Lyndon 串本身在该串后缀集合中的最小性是严格的。接下来我们探究一些 Lyndon 串的性质。
Lyndon 串的结论一：Lyndon 串不含有 Border。
因为一个串的 Border 既是该串的严格后缀也是该串的严格前缀，前者必须大于原串，后者一定小于原串，二者矛盾。
Lyndon 串的结论二：对于 Lyndon 串 \(t\) 和任意串 \(s\)，有 \(s
页:
[1]