P6656 【模板】Runs

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

无

无

对于 $60\%$ 的数据，$|S| \le 2 \times 10^5$。 对于 $100\%$ 的数据，$|S| \le 10^6$。