题目描述
给出只包含小写字母 a,b 的两个字符串 s,t,q 次询问,每次询问 s[l…r] 和 t 的最长公共子串长度。
输入格式
输入共 q+3 行。
第一行一个字符串 s。
第二行一个字符串 t。
第三行一个整数 q。
接下来的 q 行,每行两个整数 li,ri(1≤li≤ri≤∣s∣),表示一次询问。
输出格式
输出共 q 行。
第 i 行表示 s[li…ri] 和 t 的最长公共子串长度。
样例
aaba
aaaabbbaa
3
1 4
1 3
2 4
3
3
2
数据范围与提示
测试点编号 |
∣s∣,∣t∣≤ |
q≤ |
1 |
50 |
2,3 |
2×103 |
4,5 |
2×105 |
10 |
6∼10 |
2×105 |