#3298. 「BJOI2020」封印

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

题目描述

给出只包含小写字母 a,b 的两个字符串 s, t q 次询问,每次询问 s[l \dots r] t 的最长公共子串长度。

输入格式

输入共 q+3 行。

第一行一个字符串 s

第二行一个字符串 t

第三行一个整数 q

接下来的 q 行,每行两个整数 l_i, r_i(1\le l_i \le r_i \le |s|) ,表示一次询问。

输出格式

输出共 q 行。

i 行表示 s[l_i \dots r_i] t 的最长公共子串长度。

样例

样例输入

aaba
aaaabbbaa
3
1 4
1 3
2 4

样例输出

3
3
2

数据范围与提示

测试点编号 \vert s\vert , \vert t\vert \le q\le
1 50
2,3 2\times 10^3
4,5 2\times 10^5 10
6\sim 10 2\times 10^5