Contents

1. 1. 今天是个特殊的日子，5月20日，虽然我没过过这个节日不过还是做两道符合这个日子的题目吧！O(∩_∩)O~
2. 2. Input
3. 3. Output
4. 4. Input示例
5. 5. Output示例
6. 6. 定义状态：
7. 7. 状态转移方程：

今天是个特殊的日子，5月20日，虽然我没过过这个节日不过还是做两道符合这个日子的题目吧！O(∩_∩)O~

51nod除了在做OJ之外，还开展了很多副业。婚姻介绍所就是其中之一。

对于一个客户，我们可以使用一个字符串来描述该客户的特质。

假设现在我们有两个客户A和B。

• A的特质字符串为：abcdefg
• B的特质字符串为：abcxyz

则A和B的匹配度f(A, B)为A和B的最长公共前缀的长度，即len(‘abc’) = 3

由于最近51nod经费紧张，所以夹克大老爷设计了一种压缩算法以节约内存。

所有用户的特质字符串都被存储在了一个长为n的字符串S中。(n <= 1000)用户的特质使用一个整数p表示，表示该用户的特质字符串为S[p…n - 1]。

现给定字符串S，与q次查询（ai, bi分别为合法的用户特质整数）。请输出q次查询分别对应的客户匹配度。

Input

现给定字符串长度n，与字符串S。接下来是整数q，代表接下来有q次查询。
下面q行有两个整数ai, bi。代表查询特质为ai与bi的用户的匹配度。

1 <= n <= 1000
1 <= q <= 10^6

输入数据全部合法。

Output

每一行输出一个用户匹配度整数。

Input示例

12
loveornolove
5
3 7
0 0
9 1
3 1
9 5

Output示例

0
12
3
0
0

定义状态：

s[i][j]代表字符串[i , n-1]和[j , n-1]前缀相同的最大个数

状态转移方程：

s[i][j] = str[i] == str[j] ? s[i+1][j+1] + 1 : 0;

#include <cstdio>
#include <cstring>

const int MAXN = 1010;
int s[MAXN][MAXN];
char str[MAXN];

int main(){

    int n, m, q;
    scanf("%d%s", &n, str);
memset(s, 0, sizeof(s));//边界处理
//主要是为了将第n列和第n行s[n][0 , n] = 0,s[0 , n][n] 把第n列的状态，第n行的状态初始化为0(字符串中最后一个字母是第n -1 个)
    for(int i = n - 1; i >= 0; i--){//从后往前(类似从底往上),先把子问题解决再解决大问题
        for(int j = n - 1; j >= 0; j--){
            s[i][j] = str[i] == str[j] ? s[i+1][j+1] + 1 : 0;
        }
    }

    scanf("%d", &q);
    while(q--){
        scanf("%d%d", &m, &n);
        printf("%d\n", s[m][n]);
    }
    return 0;
}