E - 部分文字列
Editorial
/
Time Limit: 2 sec / Memory Limit: 128 MB
問題文
square1001「E869120は全て文字のcharacterが違うが、square1001は文字のcharacterが一致するものが2個もある!」
E869120「ということは、部分文字列の種類数も違うのでは…」
square1001「たとえば1001では、2文字目だけの'0'と3文字目だけの'0'が重複しているのではないか!('1'もそうです)」
ということで、今回は文字列Sの部分文字列を全て列挙し、文字列の重複を1つにまとめて数えたときのの文字数の合計を求めてください。
例えば、"aba"のとき、{"a","b","a","ab","ba","aba"}の6通りが考えられますが、"a"は重複しているので、
部分文字列としては5種類が考えられます。
{"a","b","ab","ba","aba"}の合計1+1+2+2+3= 9文字となります。
注意:答えは32ビット整数型に収まらない可能性があります。
入力
入力は以下の形式で標準入力から与えられる。
S
- 1 行目には, 調べる文字列S が与えられる。
出力
出力は以下の形式で標準出力に従うこと。
- 部分文字列として考えられる文字列(重複は1つにまとめて数える)の合計の長さを1行で出力してください。
- ただし、答えは32ビット整数型に収まらない可能性があります。
制約
- 1 ≦ |S| ≦ 100,000
- 含まれる文字の種類はalphabetの小文字だけ
小課題
小課題 1 [ 15 点 ]
- 1≦|S|≦100 を満たす。
小課題 2 [ 35 点 ]
- 1≦|S|≦2,000 を満たす。
小課題 3 [ 50 点 ]
- 追加の制約はない。
入力例1
abc
出力例1
10
- a, b, c, ab, bc, abc が abc の部分文字列であり, 合計は 10 文字である。
入力例2
aaqqz
出力例2
33
- 重複があることに注意してください。
入力例3
atcoder
出力例3
84
問題文担当者:square1001