# Run Enumerate

AC一覧

## Problem Statement問題文

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 maximul. In other words, $(t, l - 1, r)$ and $(t, l, r + 1)$ are not satisfied the above condition.

• $S$ の $l$ 文字目から $r - 1$ 文字目の 最小 周期は $t$ であり、$r - l \geq 2t$ を満たす ($l$, $r$ は0-indexed)
• 上の条件を満たすもののうち、$l, r$ は極大である。つまり $(t, l - 1, r), (t, l, r + 1)$ は上の条件を満たさない

## Constraints制約

• $1 \leq N \leq 200,000$
• Each character of $S$ is lowercase English letters.
• $1 \leq N \leq 200,000$
• $S$ は英小文字からなる。

## Input入力

$S$

## Output出力

$M$
$t_1$ $l_1$ $r_1$
$t_2$ $l_2$ $r_2$
:
$t_M$ $l_M$ $r_M$

ただし、$M$ はrunの個数とし、またrunは $(t, l, r)$ の順で辞書順にsortして出力すること

## Sampleサンプル

abcbcba
1
2 1 6

mississippi
4
1 2 4
1 5 7
1 8 10
3 1 8

ababacaca
2
2 0 5
2 4 9

### # 4

aaaaa
1
1 0 5

Timelimit: 5 secs

Before submitting, please confirm terms and conditions