N - Number of Abbreviations
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
英小文字からなる長さ N の文字列 S=S_1 S_2 \dots S_N があります。以下の操作をちょうど 1 回行うとき、最終的な S としてありうる文字列の種類数を求めてください。
- 1 \le l \le r \le N を満たす整数 l, r を選び、S の l 文字目から r 文字目までを取り除く。つまり、操作後の S は S_1S_2\dots S_{l-1}S_{r+1}\dots S_N となる。
制約
- N は整数
- 1 \leq N \leq 5 \times 10^5
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを 1 行に出力せよ。
入力例 1
5 abbab
出力例 1
11
得られる S としてありうるものは以下の 11 通りです。
- 空文字列
a
aab
ab
abab
abb
abba
abbb
b
bab
bbab
入力例 2
5 aaaaa
出力例 2
5
入力例 3
4 utpc
出力例 3
10