P4094 [HEOI2016/TJOI2016] String

On Jiayuan’s birthday, her friends bought her a birthday gift from an online store. The gift is placed in a magic box. On the outside of the box there is a string $s$ of length $n$, and $m$ questions. Jiayuan must answer these $m$ questions correctly to open the box and get the gift, get promoted and receive a raise, become the CEO, marry a rich and handsome man, and reach the pinnacle of life. Each question has four parameters $a,b,c,d$. Among all substrings of $s[a..b]$, what is the maximum possible length of the longest common prefix with $s[c..d]$? Jiayuan is not good at such problems, so she asks you for help. How would you help her?

The first line contains two positive integers $n,m$, denoting the length of the string and the number of queries. The next line contains a string of length $n$. Then there are $m$ lines, each containing four integers $a,b,c,d$, representing a query asking for the maximum length of the longest common prefix between any substring of $s[a..b]$ and $s[c..d]$.

For each query, output the answer.

For $10\%$ of the testdata, $1 \le n,m \le 300$. For $40\%$ of the testdata, $1 \le n,m \le 3{,}000$, and the string contains only `a`, `b`. For $100\%$ of the testdata, $1 \le n,m \le 100{,}000$, the string contains only lowercase English letters, $a \le b$, $c \le d$, and $1 \le a,b,c,d \le n$. Translated by ChatGPT 5