Runs 学习笔记

· · 题解

本文以文字说明为主，记号较少，可能存在一些非正式表述，请谅解。

前置知识：字符串哈希或后缀数组，脑子。

记 s_{i} 为字符串 s 的第 i 个字符（1 下标），默认字符串的长度是 n。

记 s_{l,r} 为从 l 到 r 的字符组成的子串。

称一个字符串的 i 后缀为从第 i 个字符开始的后缀，i 前缀则是到第 i 个字符终止的前缀。

如果没有讨论越界问题，默认 s_0=s_{n+1}=-\inf，即小于任意字符。

首先，什么是 runs？

一个字符串 s 中的一个 runs 是一个循环子串，例如 aabcabcabb 中 abcabcab 这个子串就是一个 runs。

一个 runs 必然存在最小周期，记最小周期长度为 p，对应子串是 s_{l,r}，则一个 runs 还要满足：

所以，对于串 aabcabcabb 而言，子串 abcab 和 abcabca 都不能算作 runs。

接下来讨论如何去求所有 runs。

如果现在已经找到了某个 runs 的某个最小周期 s_{i,j}，那么可以通过对 i 后缀和 j+1 后缀求一次最长公共前缀来向右扩展，以及对 i-1 前缀和 j 前缀求最长公共后缀来向左扩展，最后检查是否满足 runs 的条件就能找到这个 runs。

任意一个在 runs 范围中且长度为 p 的子串其实都能被称为 "周期"，下文直接称其为周期。

记上述操作为一次检查。要想找出所有 runs，只需要检查所有可能的周期即可。

任何一个 runs 都有 p 种周期，他们互为循环同构的串，仍然假设这个 runs 是 s_{l,r}。

从其中最小的串入手，假设这是 s_{i,j}（因为长度至少是 2p 所以这样的串必然存在）。

这玩意其实可以叫最小表示法，一般的求法是重复原串两遍，取 1\sim n 后缀中最小的后缀再截取 n 前缀就行。

但是由于这是 runs，可以证明这还是一个 Lyndon Word，即所有后缀都比原串大，以下是简要证明：

首先说明对于任意非空串 a,b，(a+b)^k+a（k \in \Z^+） 一定不是一个最小表示法，考虑 a+(a+b)^k 与 (b+a)^k+a 这两个串就能推出矛盾。

反证法，不妨假设我们找到的串是 r 有一个后缀 s 比原串小。因为任何循环同构都大于等于 r，可以推出 s 是 r 的前缀，即 s 是 r 的一个 \text{border}。

首先 |s| 不能是 |r| 的因数，否则 |r| 就不是最小周期；

若 |s|<\frac{|r|}2，则 r 可以写成 s+t+s，必然不是最小表示法；

若 |s|>\frac{|r|}2, 记 r=s+t，则 s 必然有周期 t，取 t 长度为 |s| \bmod |t| 的前缀为 a，记剩下的为 b，则 s=(a+b)^k+a，r=(a+b)^{k+1}+a，也必然不是最小表示法。

所以对于任意 i+1 \leq k \leq j，k 后缀要大于 i 后缀。

那么 j+1 后缀是 i 后面第一个可能比 i 后缀小的后缀。

同时可以发现 j+1 后缀与 i 后缀的大小关系取决于 s_{r+1} 与 s_{r+1-p} 的大小关系（就是之前取最长公共前缀的两个后缀）。

所以，通过找到所有 i 后缀后面第一个比他小的后缀，并且检查对应区间，可以找出所有 s_{r+1}<s_{r+1-p} 的 runs。

对于 s_{r+1}<s_{r+1-p} 的 runs，从最大的周期（即反转字符大小关系下的最小，注意此时空字符应当大于所有字符）入手即可。即找到所有 i 后缀后面第一个比他大的后缀，就可以找出所有这一类 runs。

不存在 s_{r+1}=s_{r+1-p} 的情况，所以，通过检查至多 2n 次，可以找出所有 runs。

这也就是 runs 数量小于等于 2n 的证明。

最后，如果这个 runs 包含 k 个完整周期，那么最小/大周期也会出现至少 k-1 次，所以记得去重。

讨论一些实现细节。

第一种实现是使用后缀排序。需要写正串和反串两遍 SA。通过写 SA-IS 加上四毛子可以做到线性求 runs。

第二种是直接字符串哈希，使用二分哈希/倍增哈希 O(\log n) 求最长公共前后缀以及后缀比较。使用单调栈就只需要 O(n) 次比较，总复杂度也是 O(n\log n)。

代码就不放了，哈希应该不至于不会写吧，记得去重。

后记：其实并不是初学 runs，纯粹是昨晚和同学口胡 runs 后几天心血来潮写了一篇。