We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. How Many Substrings?

How Many Substrings?

Problem
Submissions
Leaderboard
Discussions
Editorial

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 1: The only substring of a is itself, so we print on a new line.
  2. 1 4: The substrings of abaa are a, b, ab, ba, aa, aba, baa, and abaa, so we print on a new line.
  3. 1 1: The only substring of a is itself, so we print on a new line.
  4. 1 4: The substrings of abaa are a, b, ab, ba, aa, aba, baa, and abaa, so we print on a new line.
  5. 0 2: The substrings of aab are a, b, aa, ab, and aab, so we print on a new line.

Author

SkyDec

Difficulty

Expert

Max Score

100

Submitted By

6567

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature