#P9042. [2017年备战省选]a
[2017年备战省选]a
题目描述
给定一个长度为 的 01 串。每个位置 对应以 结尾、从串首开始的一个前缀。两个不同前缀的相似度是它们的最长公共后缀长度。
对于每次给出的区间 ,在结束位置均落在区间内的前缀中,求两个不同前缀所能达到的最大相似度。
输入格式
第一行两个整数 ,表示串长和询问数。第二行一个长度为 的 01 串。
接下来 行,每行两个正整数 ,满足 。
输出格式
每次询问输出一行一个整数,表示最大相似度。
样例 1
4 2
0101
1 3
2 4
1
2
原题的第二组样例见原比赛样例数据文件夹。
数据范围
| 测试点 | ||
|---|---|---|
| 1–2 | 100 | |
| 3–4 | 300 | 1000 |
| 5–6 | 5000 | |
| 7–10 | 100000 | 300 |
| 11–14 | 50000 | |
| 15–20 | 100000 | |