#P4556. [Tjoi2016&Heoi2016]字符串

    ID: 2022 传统题 2000ms 128MiB 尝试: 2111 已通过: 598 难度: 8 上传者: 标签>CF2500提高+/省选-二分答案后缀数组倍增计数排序Kasai 算法LCP+RMQST 表二分查找可持久化线段树路径复制前缀版本作差

[Tjoi2016&Heoi2016]字符串

题目描述

佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。
箱子外边写了一个长为 nn 的字符串 ss 和 mm 个问题。
佳媛姐姐必须正确回答这 mm 个问题,才能打开箱子拿到礼物,升职加薪,出任CEO,嫁给高富帅,走上人生巅峰。

每个问题均有 a,b,c,da,b,c,d 四个参数,问你子串 s[a…b]s[a \dots b] 的所有子串和 s[c…d]s[c \dots d] 的最长公共前缀的长度的最大值是多少?

佳媛姐姐并不擅长做这样的问题,所以她向你求助,你该如何帮助她呢?

输入格式

第一行输入两个正整数 n,mn,m,分别表示字符串的长度和询问的个数。
第二行输入一个长为 nn 的字符串 ss。 接下来 mm 行,每行有 44 个数 a,b,c,da,b,c,d,表示询问s[a…b]s[a \dots b] 的所有子串和 s[c…d]s[c \dots 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

数据规模与约定

对于 100%100\% 的数据,1≤n,m≤1051\leq n,m \leq 10^5。

保证字符串中仅含有小写英文字母,a≤ba\leq b,c≤dc \leq d,1≤a,b,c,d≤n1 \leq a,b,c,d \leq n。