Number of Substrings

AC一覧

Problem Statement
問題文

Given a length $N$ string $S$. Count the number of distinct substrings of $S$.

長さ $N$ の文字列 $S$ が与えられます。$S$ の相異なる部分文字列の個数を求めてください。

Constraints
制約

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

Input
入力

$S$

Output
出力

$ans$

Sample
サンプル

# 1

abcbcba
21

# 2

mississippi
53

# 3

ababacaca
33

# 4

aaaaa
5

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions