Run 枚举

【题目描述】

给定一个长度为 $N$ 的字符串 $S$。请枚举 $S$ 的所有 run。换言之，请枚举所有满足以下条件的元组 $(t, l, r)$。

• $S[l..r-1]$ 的最小周期为 $t$，并且满足 $r - l \geq 2t$。
• $l$ 与 $r$ 都是极大的。也就是说，$(t, l - 1, r)$ 与 $(t, l, r + 1)$ 都不满足上述条件。

【输入】

输入以如下格式给出：

$S$

【输出】

输出以如下格式给出：

$M$
$t_1$ $l_1$ $r_1$
$t_2$ $l_2$ $r_2$
:
$t_M$ $l_M$ $r_M$

其中 $M$ 为 run 的个数，各个 run 以 $(t, l, r)$ 元组的形式按字典序输出。

【输入样例】

abcbcba

【输出样例】

1
2 1 6

【输入样例2】

mississippi

【输出样例2】

4
1 2 4
1 5 7
1 8 10
3 1 8

【输入样例3】

ababacaca

【输出样例3】

2
2 0 5
2 4 9

【输入样例4】

aaaaa

【输出样例4】

1
1 0 5

【数据范围】

• $1 \leq N \leq 200,000$
• $S$ 的每个字符都是小写英文字母。

【来源】

Library Checker（yosupo06） runenumerate