【luogu P6656】【LOJ 173】【模板】Runs（字符串）（Lyndon 串）

【模板】Runs

题目链接：luogu P6656 / LOJ 173

题目大意

给你一个字符串，要你求它所有的 Runs。

思路

本文也是参考着 command_block 大神的博客 进行学习的，只是书写一下自己的个人理解。

首先有一（亿）些关于 Lyndon 的知识建议先看看。

然后就开始讲了咯。
（文中许多东西建立在前面这篇文章的基础上，所以讲也不会再讲之前的内容）

定义

Run & Runs

一个三元组 $r=(l,r,p)$ 是 $\mathrm{run}$ 当且仅当：
字符串 $s$ 中 $l\sim r$ 形成的子串，$p$ 是最小循环节，而且 $2p⩽r-l+1$。
而且这个串是不能延伸的，具体一点就是 $s_{l-1}\ne s_{l+p-1},s_{r+1}\ne s_{r-p+1}$。
然后一个字符串所有的 $\mathrm{run}$ 就组成了 $\mathrm{Runs}$。

一个 run 的指数是 $e_r=\frac{r-l+1}{p}$
${\rho }_{\mathrm{run}}(n)$ 是长度为 $n$ 的字符串至多有的 $\mathrm{run}$ 的个数。
${\sigma }_{\mathrm{run}}(n)$ 是长度为 $n$ 的字符串的 $\mathrm{run}$ 的指数和的最大值。

Lyndon Root

这个东西一般是指一个 $\mathrm{run}$ 的 Lyndon Root。
是一个在 $\mathrm{run}$ 所在区间的子区间，而且长度为 $p$，还是 Lyndon Word。
意思其实就是说是 $\mathrm{run}$ 的循环节的最小表示的那个。

然后不难看出对于任意一个 $r$ 至少有一个 Lyndon Root，而且每一个之间其实是相等的，只是位置不同。

Run

为了方便书写，我们设 Lyndon Word 为 $\mathrm{Ly}$，Lyndon Root 为 $\mathrm{LyR}$。

首先有个性质，就是两个周期相同为 $p$ 的 run 的交的长度是 $<p$ 的。
因为如果 $>p$ 我们可以在交中选一个循环节扩展，就矛盾了。
（性质 $1$）

---

接着我们就要证明我们最重要的东西了：
${\rho }_{\mathrm{run}}(n)<n,{\sigma }_{\mathrm{run}}(n)⩽3n-3$

首先我们之前有一个说那个比较大小可以重载的（${<}_0,{<}_1$），我们找找有关的性质。
然后因为有相反的，所有我们在前面比较完有一个空了的时候就要区别开来，所以我们会有一个占位符 $\text{\$}$，在 ${<}_0$ 里面我们让 $\text{\$}$ 字典序最小，${<}_1$ 里面就是最大。

---

那我们就有这么一个小定义：
${\mathrm{Ly}}_{s,f}(i)$ 为 $[i,j]$，其中 $j$ 是 $\max \{k|s[i,k]$ 是关于 ${<}_f$ 的 $\mathrm{Ly}\}$
也就是在 ${<}_f$ 意义下，起始位置为 $i$ 的最长的 $\mathrm{Ly}$ 子串。

然后有一个事情就是正反两个字典序只能有一个会找到长度大于 $1$ 的 $\mathrm{Ly}$。
形式化就是：只有恰好一个 $f\in \{0,1\}$ 使得 ${\mathrm{Ly}}_{s,f}(i)=[i,i],{\mathrm{Ly}}_{s,1-f}(i)=[i,j](j>i)$
你就看后面第一个跟 $s_i$ 不同的字符（因为有占位符所以必定存在），如果是在这个意义下是小于那就不能加上，所以只有自己的位置，否则至少也有那个不同的位置是可以作为 $\mathrm{Ly}$ 的。
（性质 $2$）

---

然后就是对于一个 $\mathrm{run}$，设为 $r=(l,r,p)$，找到 $f\in \{0,1\}$ 使得 $s_{r+1}{<}_f{s}_{r-p+1}$，那么 $r$ 所有关于 ${<}_f$ 的 $\mathrm{LyR}$（设为 $[i,j]$） 都跟 ${\mathrm{Ly}}_{s,f}(i)$ 相等。
因为是 $\mathrm{Ly}$ 循环节嘛，我们可以表示为 $u^c{u}^{\prime }$（不用找 $\mathrm{Ly}$ 循环节），其中 $u^{\prime }$ 是 $u$ 严格前缀（就是不能等于）

你会发现它长得很像 Duval 算法里面的那个形式。
然后如果你用 $1-f$，你会根据性质 $2$ 发现都是一个字符，没有意义。

我们也发现这个 $f$ 它这样在 $\mathrm{run}$ 中有特殊的地方，于是我们把这个 ${<}_f$ 记为 $r$ 的正序。
（性质 $3$）

---

然后再设一个 $\mathrm{LyRs}(r)$ 表示 $r$ 所有正序的 $\mathrm{LyR}$，除去 $l$ 开头的（如果有）。
然后我们会发现 $|\mathrm{LyRs}(r)|⩾\lfloor e_r-1\rfloor ⩾1$
其实挺显然的？
首先第二个跟第三个那肯定没问题，毕竟你 $2p\le len$，那肯定 $e_r⩾2$ 了。
然后是第一个跟第二个，那 $|\mathrm{LyRs}(r)|$ 就是看有多少个循环节，会发现跟 $e_r$ 差不多。
但是由于可能会除去一个 $l$ 开头的，所以要减一，而且可能跑不满一个新的循环节，所以是下取整。
（性质 $4$）

---

对于两个不同的 $\mathrm{run}$（$r=(l,r,p),r^{\prime }=(l^{\prime },r^{\prime },p^{\prime })$），它们的 $\mathrm{LyRs}$ 的左端点集合不会有交。
设左端点集合为 $\mathrm{Beg}(x)$，就是 $\mathrm{Beg}(\mathrm{LyRs}(r))\cap \mathrm{Beg}(\mathrm{LyRs}(r^{\prime }))=\varnothing$。

考虑反证法，设存在且是位置 $i$，那两个 $\mathrm{LyR}$ 设是 $[i,j],[i,j^{\prime }]$。
然后设 ${<}_f$ 是 $r$ 的正序，然后你会发现 ${\mathrm{Ly}}_{s,f}(i)$ 就是两个的表示？
但是显然两个的这个值应该要不一样啊，不然就是同一个 $\mathrm{run}$ 了。
那只能是一个正序一个反序，所以另一个就是 ${\mathrm{Ly}}_{s,1-f}(i)$。
那必然有一个 $[i,i]$，设 $j=i$，就有 $j^{\prime }>i$。（性质 $2$）
那因为 $[i,j^{\prime }]$ 是 $\mathrm{Ly}$，所以自然 $s_i\ne s_{j^{\prime }}$，再从性质 $3$ 会有 $r$ 的循环节是 $p=|[i,i]|=1$，$r^{\prime }$ 的循环节就是 $p^{\prime }=|[i,j^{\prime }]|=j-i+1$。
那周期性一下：$s_i=s_{i-1}=s_{i-1+(j-i+1)}=s_{j^{\prime }}$，与 $s_i=s_{j^{\prime }}$ 矛盾。
所以就证好了。
（性质 $5$）

---

不难通过性质 $5$ 发现，最多每个左端点都被占了，再把 $l$ 给去掉，所以我们可以证明：
${\rho }_{\mathrm{run}}(n)<n$
再看看什么没用上，性质 $4$。
不难看出用到的是 $|\mathrm{LyRs}(r)|⩾\lfloor e_r-1\rfloor$。
下取整不行换一下 $|\mathrm{LyRs}(r)|⩾\lfloor e_r-1\rfloor ⩾e_r-2$
推广到所有 $\mathrm{run}$：$\sum _{r\in \mathrm{runs}(s)}{e}_r-2⩽\sum _{r\in \mathrm{runs}(s)}|\mathrm{LyRs}(r)|⩽n-1$
再结合一下 $|\mathrm{runs}(\mathrm{s})|⩽n-1$，把 $-2$ 提出来：
$(\sum _{r\in \mathrm{runs}(s)}{e}_r)-2(n-1)⩽n-1$
${\sigma }_{\mathrm{run}}(n)-2n+2⩽n-1$
${\sigma }_{\mathrm{run}}(n)⩽3n-3$
搞定！
（性质 $6$）

Ex

${\rho }_{\mathrm{run},k}(n)<\frac{n}{k-1}$，${\rho }_{\mathrm{run},k}$ 表示 $e_r$ 达到 $k$ 的 $\mathrm{run}$ 的个数。
挺显然的，就结合一下占位的想法看看就知道了。

计算

假设我们直接暴力找：
就是枚举周期 $p$，然后在串中撒点（均匀撒），然后鸽笼（也许不需要）一下就知道一个大小为 $p$ 的 $\mathrm{run}$ 一定会穿过至少两个点。
那就相邻两个点之间向前向后求 $\mathrm{LCP}$，如果覆盖范围能连接起来，就找到了一个。

当然你可以用性质 $1$ 小小剪枝。

而且你会发现你枚举的周期不一定是最小周期，所以我们得排序，然后去重一下。

然后如果二分+Hash搞就是 $n{\log }^{2}n$，后缀数组搞就是 $n\log n$。
感觉不优。

---

在介绍新的求法之前，不妨看看这么一个问题，如何快速求所有 ${\mathrm{Ly}}_s(i)$。
考虑从那个合并的角度来看，从右往左扫，每次加进去一个字符（然后你用一个栈维护前面的 $\mathrm{Ly}$）。
然后不停的查看是否能合并，然后这个地方比大小我们就先二分+Hash找到不同的位置，然后用当前的 $f$ 判断一下即可。

---

考虑用上一些性质，就我们可以从性质 $2$ 发现，一个 $\mathrm{run}$ 含有的 $\mathrm{Ly}$ 循环节是某个字典序下某个后缀最长 $\mathrm{Ly}$ 前缀。
而且两个不同的 $\mathrm{run}$ 的循环节肯定不同。
我们考虑直接枚举循环节，直接前后求 $\mathrm{LCP}$，这样循环节是 $O(n)$ 的。

具体一点就是枚举 $f,l$，然后由于我们求出了所有的 ${\mathrm{Ly}}_s(i)$，我们就 $\mathrm{LCP}$ 得到扩展，然后判一下是否能相交即可。
然后也是要去重。

然后由于后缀数组预处理要 $n\log n$，不如使用二分+hash，好写一点。
这里我们就是使用了 $\mathrm{Ly}$ 串构造最小循环节，可以说是一种映射，所以就把复杂度降到了 $O(n)$。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ull unsigned long long
#define di 131

using namespace std;

const int N = 1e6 + 100;
struct node {
    
	int l, r, p;
}ans[N];
char s[N];
int n, ly[N], sta[N], m, ans_num;
ull mi[N], hsh[N];

void Init() {
    
	mi[0] = 1;
	for (int i = 1; i <= n; i++) {
    
		mi[i] = mi[i - 1] * di;
		hsh[i] = hsh[i - 1] * di + s[i] - 'a'; 
	}
}

ull get(int l, int r) {
    
	return hsh[r] - hsh[l - 1] * mi[r - l + 1];
}

int getl(int x, int y) {
    
	int l = 0, r = min(x, y), re = 0;
	while (l <= r) {
    
		int mid = (l + r) >> 1;
		if (get(x - mid + 1, x) == get(y - mid + 1, y)) re = mid, l = mid + 1;
			else r = mid - 1;
	}
	return re;
}

int getr(int x, int y) {
    
	int l = 0, r = min(n - x + 1, n - y + 1), re = 0;
	while (l <= r) {
    
		int mid = (l + r) >> 1;
		if (get(x, x + mid - 1) == get(y, y + mid - 1)) re = mid, l = mid + 1;
			else r = mid - 1;
	}
	return re;
}

bool cmpS(int x, int y) {
    
	int sz = getr(x, y);
	return s[x + sz] < s[y + sz];
}

void Lyndon(bool op) {
    
	ly[n] = n;
	sta[0] = 0; sta[++sta[0]] = n + 1; sta[++sta[0]] = n;
	for (int i = n - 1; i >= 1; i--) {
    
		while (sta[0] > 1 && cmpS(i, sta[sta[0]]) == op) sta[0]--;
		sta[++sta[0]] = i;
		ly[i] = sta[sta[0] - 1] - 1;
	}
}

void slove(int x, int y) {
    
	int l = getl(x, y), r = getr(x, y);
	if (l + r >= y - x + 1) {
    
		ans[++m] = (node){
    x - l + 1, y + r - 1, y - x};
	}
}

bool cmp(node x, node y) {
    
	if (x.l != y.l) return x.l < y.l;
	if (x.r != y.r) return x.r < y.r;
	return x.p > y.p;
}

int main() {
    
	scanf("%s", s + 1); n = strlen(s + 1);
	Init();
	
	for (int op = 0; op <= 1; op++) {
    
		Lyndon(op);
		for (int i = 1; i < n; i++)
			slove(i, ly[i] + 1);
	}
	
	sort(ans + 1, ans + m + 1, cmp);
	for (int i = 1; i <= m; i++) {
    
		if (ans[i].l == ans[i - 1].l && ans[i].r == ans[i - 1].r) continue;
		ans_num++;
	}
	printf("%d\n", ans_num);
	for (int i = 1; i <= m; i++) {
    
		if (ans[i].l == ans[i - 1].l && ans[i].r == ans[i - 1].r) continue;
		printf("%d %d %d\n", ans[i].l, ans[i].r, ans[i].p);
	}
	
	return 0;
}