Rank Among the Suffixes

Difficulty: 2200 6000 ms 128 MB

strings suffix-array

Sort all suffixes of S lexicographically. Answer Q queries: what is the rank (1-based) of the suffix that starts at position i?

Input: the first line has S; the second line has Q; each of the next Q lines has a start position i.

Output: one line per query with the suffix's rank.

Constraints:

• 1 ≤ |S| ≤ 10⁵
• 1 ≤ Q ≤ 10⁵

Sample Tests

banana
2
1
2

4
3

ab
1
2

2

Read the Editorial