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.

長さ $N$ の文字列 $S$ が与えられます。$S$ のrun、つまり以下の条件を満たすタプル $(t, l, r)$ を列挙してください。

  • $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
サンプル

# 1

abcbcba
1
2 1 6

# 2

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

# 3

ababacaca
2
2 0 5
2 4 9

# 4

aaaaa
1
1 0 5

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions