- Prepare
- Algorithms
- Strings
- How Many Substrings?

# How Many Substrings?

# How Many Substrings?

Consider a string of characters, , of where each character is indexed from to .

You are given queries in the form of two integer indices: and . For each query, count and print the number of different substrings of in the inclusive range between and .

**Note:** Two substrings are *different* if their sequence of characters differs by at least one. For example, given the string `aab`

, substrings `a`

and `a`

are the same but substrings `aa`

and `ab`

are different.

**Input Format**

The first line contains two space-separated integers describing the respective values of and .

The second line contains a single string denoting .

Each of the subsequent lines contains two space-separated integers describing the respective values of and for a query.

**Constraints**

- String consists of lowercase English alphabetic letters (i.e.,
`a`

to`z`

) only.

**Subtasks**

- For of the test cases,
- For of the test cases,
- For of the test cases,

**Output Format**

For each query, print the number of different substrings in the inclusive range between index and index on a new line.

**Sample Input 0**

```
5 5
aabaa
1 1
1 4
1 1
1 4
0 2
```

**Sample Output 0**

```
1
8
1
8
5
```

**Explanation 0**

Given `aabaa`

, we perform the following queries:

`1 1`

: The only substring of`a`

is itself, so we print on a new line.`1 4`

: The substrings of`abaa`

are`a`

,`b`

,`ab`

,`ba`

,`aa`

,`aba`

,`baa`

, and`abaa`

, so we print on a new line.`1 1`

: The only substring of`a`

is itself, so we print on a new line.`1 4`

: The substrings of`abaa`

are`a`

,`b`

,`ab`

,`ba`

,`aa`

,`aba`

,`baa`

, and`abaa`

, so we print on a new line.`0 2`

: The substrings of`aab`

are`a`

,`b`

,`aa`

,`ab`

, and`aab`

, so we print on a new line.