3943: Runs
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
定义一个字符串 $|S|$ 里的一个 run，指其内部一段两侧都不能扩展的**周期子串**，且周期至少完整出现两次。
严格地说，一个 run 是一个 三元组 $(i,j,p)$，满足 $p$ 是 $S[i..j]$ 的最小周期，$j-i+1 \ge 2p$，且满足如下两个条件：
+ 要么 $i=1$，要么 $S[i-1]\ne S[i-1+p]$；
+ 要么 $j=n$，要么 $S[j+1] \ne S[j+1-p]$。
给定字符串 $S$，求他的所有 runs。
输入
一行一个字符串 $S$，保证其只由小写字母构成。
输出
第一行一个整数 $m$，表示 runs 的数量。
接下来 $m$ 行，每行三个整数 $i,j,p$ 描述一个 runs。
你应该以第一个字符的位置为第一关键词，最后一个字符的位置为第二关键词对所有的 runs 进行排序。
样例输入 复制
aababaababb样例输出 复制
7
1 2 1
1 10 5
2 6 2
4 9 3
6 7 1
7 10 2
10 11 1提示
数据范围：对于 $60\%$ 的数据，$|S| \le 2 \times 10^5$。 对于 $100\%$ 的数据，$|S| \le 10^6$。