Description

佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了
一个长为n的字符串s,和m个问题。佳媛姐姐必须正确回答这m个问题,才能打开箱子拿到礼物,升职加薪,出任CE
O,嫁给高富帅,走上人生巅峰。每个问题均有a,b,c,d四个参数,问你子串s[a..b]的所有子串和s[c..d]的最长公
共前缀的长度的最大值是多少?佳媛姐姐并不擅长做这样的问题,所以她向你求助,你该如何帮助她呢?

Input

输入的第一行有两个正整数n,m,分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来
m行,每行有4个数a,b,c,d,表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。1<=n,m<=100,000,
字符串中仅有小写英文字母,a<=b,c<=d,1<=a,b,c,d<=n

Output

 对于每一次询问,输出答案。

Sample Input

5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4

Sample Output

1
1
2
2
2
看了一会题目 发现不会做 看了眼标签 好大概yy了一个sa+主席树的做法 主要是二分答案没想到
首先做SA 然后针对每个rk数组建立主席树可以想象为横坐标是下标纵坐标是rk里面的数
那么每次做的时候相当于先二分一个答案 然后求一下c串在sa数组中往前往后能延伸多远求出这个L,R之后在主席树rt[a-1],rt[b-len+1]之间判断下L,R区间是否存在后缀即可

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论