Problem Description

Original Meaning

cdm1020 is a shut-in. His favorite thing in daily life is chatting (and copying) in group chats.

He took the chat logs from a group he recently chatted in, and used some mysterious compression algorithm to compress these chat logs into a string of length $n$. Because he is a chuunibyou-style fan, this string contains only $7$ kinds of characters: $\mathtt{f,z,o,u,t,s,y}$. Because of his obsession with suffix data structures, he is only interested in the suffixes of this string. He defines the index of a suffix to be $i$ if and only if the interval of the string it represents is $[i,n]$.

cdm1020 defines a pair of suffixes $(i,j)$ to be “$k$-level copying” if and only if the length of the longest common prefix of suffix $i$ and suffix $j$ is at least $k$. In other words, a pair of $k$-level copying suffixes is also $k-1,k-2,k-3,\cdots,1,0$-level copying.

Now he wants to ask: among the suffixes with indices in $(l,r)$, how many pairs of suffixes are $k$-level copying.

One-Sentence Meaning

Given a string of length $n$ over the alphabet $\mathtt{f,z,o,u,t,s,y}$ and a query parameter $k$, for multiple queries $(l,r)$, find among the suffixes with indices in $(l,r)$ how many pairs of suffixes have LCP (longest common prefix) length at least $k$.

A suffix has index $i$ if and only if it represents the characters in the interval $(i,n)$.

Input Format

The first line contains three positive integers $n,m,k$, representing the string length $n$, the number of queries $m$, and the query parameter $k$.

The second line contains a string of length $n$, which is the string you need to process.

The next $m$ lines each contain two positive integers $l,r$, representing the query interval $l,r$.

Output Format

Output $m$ lines, each containing a positive integer, representing the number of suffix pairs in the query interval whose LCP length is at least $k$.

20 15 3
oouuoouuoouuoouuoouu
10 16
2 15
4 13
6 7
4 12
12 14
12 13
7 19
1 5
6 13
1 15
9 15
11 15
1 19
15 18

3
18
8
0
6
0
0
12
1
4
21
3
1
32
0

Hint

Constraints and Notes

For all testdata, $1\leq l\leq r\leq n \leq 3×10^6$, $1\leq k \leq n \leq 3×10^6$, $1\leq m \leq 10^5$, $1 \leq n^2m \leq 10^{15}$.

It is guaranteed that the input string contains only the $7$ lowercase letters $\mathtt{f,z,o,u,t,s,y}$.

Translated by ChatGPT 5