A6676. 「雅礼集训 2017 Day7」事情的相似度
编程题
提高+/省选-
知识点
题目描述
人的一生不仅要靠自我奋斗，还要考虑到历史的行程。
历史的行程可以抽象成一个 01 串，作为一个年纪比较大的人，你希望从历史的行程中获得一些姿势。
你发现在历史的不同时刻，不断的有相同的事情发生。比如，有两个人同时在世纪之交 11 年的时候上台，同样喜欢与洋人谈笑风生，同样提出了以「三」字开头的理论。
你发现，一件事情可以看成是这个 01 串的一个前缀，这个前缀最右边的位置就是这个事情的结束时间。
两件事情的相似度可以看成，这两个前缀的最长公共后缀长度。
现在你很好奇，在一段区间内结束的事情中最相似的两件事情的相似度是多少呢？
历史的行程可以抽象成一个 01 串，作为一个年纪比较大的人，你希望从历史的行程中获得一些姿势。
你发现在历史的不同时刻，不断的有相同的事情发生。比如，有两个人同时在世纪之交 11 年的时候上台，同样喜欢与洋人谈笑风生，同样提出了以「三」字开头的理论。
你发现，一件事情可以看成是这个 01 串的一个前缀，这个前缀最右边的位置就是这个事情的结束时间。
两件事情的相似度可以看成，这两个前缀的最长公共后缀长度。
现在你很好奇，在一段区间内结束的事情中最相似的两件事情的相似度是多少呢？
输入格式
第一行两个整数 $ n $、$ m $，表示串长和询问个数。
第二行长度为 $ n $ 的 01 串，表示历史的行程。
接下来 $ m $ 行，每行两个正整数 $ l $、$ r $ 表示询问的区间，包括端点，保证 $ 1 \leq l < r \leq n $。
第二行长度为 $ 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 $ | $ 100 $ |
|3 ~ 4| $ 300 $ | $ 1000 $ |
|5 ~ 6| $ 5000 $ | $ 5000 $ |
|7 ~ 10| $ 100000 $ | $ 300 $ |
|11 ~ 14| $ 50000 $ | $ 50000 $ |
|15 ~ 20| $ 100000 $ | $ 100000 $ |
|:---:|:---:|:---:|
|1 ~ 2| $ 100 $ | $ 100 $ |
|3 ~ 4| $ 300 $ | $ 1000 $ |
|5 ~ 6| $ 5000 $ | $ 5000 $ |
|7 ~ 10| $ 100000 $ | $ 300 $ |
|11 ~ 14| $ 50000 $ | $ 50000 $ |
|15 ~ 20| $ 100000 $ | $ 100000 $ |