Source: Libre OJ 173
定义一个字符串 |S| 里的一个 run,指其内部一段两侧都不能扩展的周期子串,且周期至少完整出现两次。
严格地说,一个 run 是一个 三元组 (i,j,p),满足 p 是 S[i..j] 的最小周期,j−i+1≥2p,且满足如下两个条件:
- 要么 i=1,要么 S[i−1]≠S[i−1+p];
- 要么 j=n,要么 S[j+1]≠S[j+1−p]。
给定字符串 S,求他的所有 runs。
Input
一行一个字符串 S,保证其只由小写字母构成。
Output
第一行一个整数 m,表示 runs 的数量。
接下来 m 行,每行三个整数 i,j,p 描述一个 runs。
你应该以第一个字符的位置为第一关键词,最后一个字符的位置为第二关键词对所有的 runs 进行排序。
Example
Input
aababaababb
Output
7
1 2 1
1 10 5
2 6 2
4 9 3
6 7 1
7 10 2
10 11 1
Scoring
对于 60% 的数据,|S|≤2×105。
对于 100% 的数据,|S|≤106。