9036: [yosupo] String - Run Enumerate
[Creator : ]
Description
Given a length $N$ string $S$. Please enumerate the runs of $S$. In other words, please enumerate tuples $(t, l, r)$ that satisfy the following conditions.
- The minimum period of the $S[l..r-1]$ is $t$, and $r - l \geq 2t$ is satisfied.
- $l$ and $r$ are maximal. In other words, $(t, l - 1, r)$ and $(t, l, r + 1)$ do not satisfy the above condition.
- The minimum period of the $S[l..r-1]$ is $t$, and $r - l \geq 2t$ is satisfied.
- $l$ and $r$ are maximal. In other words, $(t, l - 1, r)$ and $(t, l, r + 1)$ do not satisfy the above condition.
Input
$S$
Output
$M$
$t_1$ $l_1$ $r_1$
$t_2$ $l_2$ $r_2$
:
$t_M$ $l_M$ $r_M$
Here, $M$ is the number of runs, and runs are printed as $(t, l, r)$ tuples in lexicographical order.
$t_1$ $l_1$ $r_1$
$t_2$ $l_2$ $r_2$
:
$t_M$ $l_M$ $r_M$
Here, $M$ is the number of runs, and runs are printed as $(t, l, r)$ tuples in lexicographical order.
Constraints
$1 \leq N \leq 200,000$
Each character of $S$ is lowercase English letters.
Each character of $S$ is lowercase English letters.
Sample 1 Input
abcbcba
Sample 1 Output
1
2 1 6
Sample 2 Input
mississippi
Sample 2 Output
4
1 2 4
1 5 7
1 8 10
3 1 8
Sample 3 Input
ababacaca
Sample 3 Output
2
2 0 5
2 4 9
aaaaa
1
1 0 5
HINT
相同题目：yosupo。