A6676 | $「雅礼集训 2017 Day7」事情的相似度$

时间限制4s

内存限制1024MB

通过 / 提交0/0

题目描述

人的一生不仅要靠自我奋斗，还要考虑到历史的行程。 历史的行程可以抽象成一个 01 串，作为一个年纪比较大的人，你希望从历史的行程中获得一些姿势。 你发现在历史的不同时刻，不断的有相同的事情发生。比如，有两个人同时在世纪之交 11 年的时候上台，同样喜欢与洋人谈笑风生，同样提出了以「三」字开头的理论。 你发现，一件事情可以看成是这个 01 串的一个前缀，这个前缀最右边的位置就是这个事情的结束时间。 两件事情的相似度可以看成，这两个前缀的最长公共后缀长度。 现在你很好奇，在一段区间内结束的事情中最相似的两件事情的相似度是多少呢？

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

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

输入 #1

输出 #1

1
2

C++ 编辑器

输入

输出