B - Substring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

英小文字からなる文字列 S が与えられます。S の空でない部分文字列は何種類ありますか？

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

制約

  • S は英小文字からなる長さ 1 以上 100 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。

入力例 1

yay

出力例 1

5

S の空でない部分文字列は以下の 5 種類です。

  • a
  • y
  • ay
  • ya
  • yay

入力例 2

aababc

出力例 2

17

入力例 3

abracadabra

出力例 3

54

Score: 200 points

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

  • S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

S

Output

Print the answer.

Sample Input 1

yay

Sample Output 1

5

S has the following five different non-empty substrings:

  • a
  • y
  • ay
  • ya
  • yay

Sample Input 2

aababc

Sample Output 2

17

Sample Input 3

abracadabra

Sample Output 3

54