This page is still under construction.

Parts of this page are still being built. What you see may change.

Number of distinct substrings

Interview

Time limit1sMemory limit512 MB

Summary
Count how many different contiguous substrings appear in a lowercase string of length up to 1000.
Level

Medium5 of 10

Topics
String matching, Hash map, Sorting
Solved
No attempts yet

Problem

You are given a string SS. Write a program that counts how many distinct substrings SS has.

A substring is a contiguous piece cut out of SS, and its length must be at least 1.

For example, the substrings of ababc are a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc, and 12 of them are distinct.

Input

The first line contains the string SS. SS consists of lowercase letters only, and its length is at most 1,000.

Output

Print the number of distinct substrings of SS on the first line.

Examples4

  1. Example 1

    Input
    ababc
    Expected output
    12

  2. Example 2

    Input
    a
    Expected output
    1

  3. Example 3

    Input
    aaaaaaaaaa
    Expected output
    10

  4. Example 4

    Input
    banana
    Expected output
    15