U639316 最长子串询问

给你一个长度为 $n$ 的字符串 $s = s_1 s_2 \ldots s_n$。 接下来有 $m$ 次询问，每次询问给你两个整数 $p$ 和 $q$。 你需要找到一个最长的整数 $z$，满足： - $p+z-1 \le n$ - $q+z-1 \le n$ - 以 $s_p$ 开头的长度为 $z$ 的子串和以 $s_q$ 开头的长度为 $z$ 的子串相同（即 $s[p..p+z-1] = s[q..q+z-1]$） 我们称整数 $z$ 为以 $s_p$ 和 $s_q$ 开头的最长公共子串长度。 特别地，如果 $s_p \neq s_q$，则不存在任何长度为正整数的同时以 $s_p$ 和 $s_q$ 开头的公共子串，则对应的 $z = 0$。

第一行，两个整数 $n$ 和 $m$，以空格分隔。 第二行，一个长度为 $n$ 的字符串 $s$。 接下来 $m$ 行，每行包含两个整数 $p$ 和 $q$，以空格分隔，表示一次询问。

对于每次询问，输出一行，包含一个整数 $z$，表示同时以 $s_p$ 和 $s_q$ 开头的最长公共子串长度。

#### 数据规模与约定 - 对于 $20\%$ 的数据，$n,m \le 20$ - 对于 $50\%$ 的数据，$n,m \le 2000$ - 对于 $100\%$ 的数据，$2 \le n \le 2 \cdot 10^5$，$1 \le m \le 2 \cdot 10^5$，字符串 $s$ 仅由小写英文字母构成，每次询问的 $p,q$ 满足 $1 \le p \lt q \le n$