#6041. 「雅礼集训 2017 Day7」事情的相似度

内存限制:1024 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

人的一生不仅要靠自我奋斗,还要考虑到历史的行程。

历史的行程可以抽象成一个 01 串,作为一个年纪比较大的人,你希望从历史的行程中获得一些姿势。

你发现在历史的不同时刻,不断的有相同的事情发生。比如,有两个人同时在世纪之交 11 年的时候上台,同样喜欢与洋人谈笑风生,同样提出了以「三」字开头的理论。

你发现,一件事情可以看成是这个 01 串的一个前缀,这个前缀最右边的位置就是这个事情的结束时间。

两件事情的相似度可以看成,这两个前缀的最长公共后缀长度。

现在你很好奇,在一段区间内结束的事情中最相似的两件事情的相似度是多少呢?

输入格式

第一行两个整数 n m ,表示串长和询问个数。
第二行长度为 n 的 01 串,表示历史的行程。
接下来 m 行,每行两个正整数 l r 表示询问的区间,包括端点,保证 1 \leq l < r \leq n

输出格式

输出 m 行,对每个询问输出一个整数表示最大的相似度。

样例

样例输入 1

4 2
0101
1 3
2 4

样例输出 1

1
2

数据范围与提示

测试点 n = m =
1 ~ 2 100
3 ~ 4 300 1000
5 ~ 6 5000
7 ~ 10 100000 300
11 ~ 14 50000
15 ~ 20 100000