#173. Runs

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zghtyarecrenj

题目描述

定义一个字符串 |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