P7361 "JZOI-1" Worshipping Gods

The New Year is coming. Xiao Xi goes up the mountain with her parents to worship gods and pray for good luck in the new year.

There are a total of $n$ gods that Xiao Xi wants to worship. Xiao Xi’s belief for each god can be represented by a lowercase letter. Putting them together forms a string $s$ indexed starting from $1$. Xiao Xi needs prayer words to worship the gods. A prayer word is defined as a non-empty contiguous substring of $s$, and its length is the length of this substring. Since worshipping only requires Xiao Xi to be serious enough, a prayer word is considered valid as long as it appears at least twice. **Note: as long as the starting positions of the two occurrences are different, it is fine even if the two substrings overlap.** However, because her parents are also present, Xiao Xi’s prayer words may sometimes be interrupted, so only the string within the interval $[l,r]$ (i.e., $s[l\dots r]$) is valid. To be prepared, Xiao Xi will carefully prepare for all possible situations. He will give $q$ queries. In each query, $l,r$ are given, and you need to ask for the length of the longest valid prayer word within the interval $[l,r]$.

The first line contains two positive integers $n,q$. The second line contains a string $s$ consisting of lowercase letters. The next $q$ lines each contain two numbers $l,r$.

Output $q$ lines. Each line outputs a non-negative integer, representing the length of the longest valid prayer word. If there is no valid prayer word, output $0$.

#### Sample Explanation: For the first query: the string in the interval is $\texttt{ababa}$, where the substring $\texttt{aba}$ appears twice, with length $3$. For the second query: the string in the interval is $\texttt{dababab}$, where the substring $\texttt{abab}$ appears twice, with length $4$. For the third query: the string in the interval is $\texttt{ababdc}$, where the substring $\texttt{ab}$ appears twice, with length $2$. For the fourth query: the string in the interval is $\texttt{babdc}$, where the substring $\texttt{b}$ appears twice, with length $1$. For the fifth query: the string in the interval is $\texttt{cdab}$, and no substring appears at least twice, so the answer is $0$. #### Constraints: For $5\%$ of the data, $n,q\le50$. For $15\%$ of the data, $n,q\le200$. For $30\%$ of the data, $n,q\le2\times10^3$. For $40\%$ of the data, $n,q\le5\times10^3$. For $65\%$ of the data, $n,q\le2\times 10^4$. For another $5\%$ of the data, all characters are the same. For $100\%$ of the data, $1 \le n\le5\times10^4$ and $1 \le q \le 10^5$. Translated by ChatGPT 5