题目翻译

题目描述

给定一个长度为 $N$ 的字符串 $S$。请枚举 $S$ 的所有 runs（极大重复串）。 换句话说，请枚举满足以下条件的三元组 $(t, l, r)$：

• 子串 $S[l \dots r - 1]$ 的最小周期为 $t$，且满足 $r - l \ge 2t$。
• $l$ 和 $r$ 是极大的。换句话说，$(t, l - 1, r)$ 和 $(t, l, r + 1)$ 不满足上述条件。（即该区间无法向左或向右扩展而保持周期 $t$ 不变）。

数据范围

• $1 \le N \le 200,000$
• $S$ 的每个字符均为小写英文字母。

输入

$S$

输出

$M$ $t_1 \ l_1 \ r_1$ $t_2 \ l_2 \ r_2$ $\vdots$ $t_M \ l_M \ r_M$

其中，$M$ 是 runs 的数量，所有的 runs 需按照 $(t, l, r)$ 的字典序输出。

无奈本蒟蒻实在是太蒻了，暂且没想出来解法，这个问题就留给各位打捞吧