#P6656. 【模板】Runs

【模板】Runs

题目描述

定义一个字符串 S|S| 里的一个 run,指其内部一段两侧都不能扩展的周期子串,且周期至少完整出现两次。

严格地说,一个 run 是一个 三元组 (i,j,p)(i,j,p),满足 ppS[i..j]S[i..j] 的最小周期,ji+12pj-i+1 \ge 2p,且满足如下两个条件:

  • 要么 i=1i=1,要么 S[i1]S[i1+p]S[i-1]\ne S[i-1+p]
  • 要么 j=nj=n,要么 S[j+1]S[j+1p]S[j+1] \ne S[j+1-p]

给定字符串 SS,求他的所有 runs。

输入格式

一行一个字符串 SS,保证其只由小写字母构成。

输出格式

第一行一个整数 mm,表示 runs 的数量。

接下来 mm 行,每行三个整数描述一个 runs:

  • 这个 runs 的第一个字符的位置
  • 最后一个字符的位置
  • 这个 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%60\% 的数据,S2×105|S| \le 2 \times 10^5

对于 100%100\% 的数据,S106|S| \le 10^6