E - 部分文字列

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

square1001E869120は全て文字の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, abcabc の部分文字列であり, 合計は 10 文字である。

入力例2

aaqqz

出力例2

33
  • 重複があることに注意してください。

入力例3

atcoder

出力例3

84

問題文担当者:square1001