4088: 「TJOI / HEOI2016」字符串
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为 $ n $ 的字符串 $ s $，和 $ m $ 个问题。佳媛姐姐必须正确回答这 $ m $ 个问题，才能打开箱子拿到礼物，升职加薪，出任 CEO，嫁给高富帅，走上人生巅峰。每个问题均有 $a, b, c, d$ 四个参数，问你子串
$s[a \ldots b]$ 的所有子串和 $s[c \ldots d]$ 的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？
输入
输入的第一行有两个正整数 $ n, m $，分别表示字符串的长度和询问的个数。
接下来一行是一个长为 $ n $ 的字符串。字符串中仅有小写英文字母。
接下来 $ m $ 行，每行有四个数 $ a, b, c, d $，表示询问 $s[a \ldots b]$ 的所有子串和 $ s[c \ldots d] $ 的最长公共前缀的最大值。
输出
对于每一次询问，输出答案。
样例输入 复制
5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4样例输出 复制
1
1
2
2
2提示
数据范围：对于所有的数据，$1 \leq n, m \leq 100000, \ a \leq b, \ c \leq d, \ 1 \leq a, b, c, d \leq n$