#PQJ58x6361. QOJ 58_6361

    ID: 3016 传统题 2000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:TJOI 2016字符串线段树

QOJ 58_6361

NOI 2016天津市代表队选拔赛day2 C 字符串 • 输入输出文件: str.in/str.out • 源文件名: str.cpp/str.c/str.pas • 时间限制: 2s 内存限制: 128M 题目描述 佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼 物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s,和m个问题。 佳媛姐姐必须正确回答这m个问题,才能打开箱子拿到礼物,升职加薪,出 任CEO,嫁给高富帅,走上人生巅峰。 每个问题均有a,b,c,d四个参数,问你子串s[a..b]的所有子串和s[c..d]的最长公 共前缀的长度的最大值是多少? 佳媛姐姐并不擅长做这样的问题,所以她向你求助,你该如何帮助她呢? 输入 输入的第一行有两个正整数n, m,分别表示字符串的长度和询问的个数。 接下来一行是一个长为n的字符串。 接下来m行,每行有4个数a,b,c,d,表示询问s[a..b]的所有子串和s[c..d]的最 长公共前缀的最大值。 输出 对于每一次询问,输出答案。 样例输入1 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 1 2 2 2 5

NOI 2016天津市代表队选拔赛day2 样例输入2 5 5 ababa 1 1 2 2 2 3 1 1 1 2 2 3 1 3 3 5 1 3 2 4 样例输出2 0 1 1 3 2 数据范围 对于10%的数据,1 ≤n, m ≤300 对于40%的数据,1 ≤n, m ≤3, 000,字符串中仅包含a和b 对于100%的数据,1 ≤n, m ≤100, 000, 字符串中仅有小写英文字母,a ≤ b, c ≤d, 1 ≤a, b, c, d ≤n 6