#P6640. [BJOI2020] 封印

[BJOI2020] 封印

题目背景

注:NOI 2020 北京队选拔赛因不可抗力因素取消,改为按前一年 CSP-S 第二轮成绩选出省队。因为出现同分,为决定最终 A 队名单,举办了加试。本题即为加试题。

题目描述

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

输入格式

输入共 q+3q+3 行。

第一行一个字符串 ss

第二行一个字符串 tt

第三行一个整数 qq

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

输出格式

输出共 qq 行。

ii 行表示 s[liri]s[l_i \dots r_i]tt 的最长公共子串长度。

aaba
aaaabbbaa
3
1 4
1 3
2 4
3
3
2

提示

测试点编号 s,t\vert s\vert , \vert t\vert \le qq\le
11 5050
2,32,3 2×1032\times 10^3
4,54,5 2×1052\times 10^5 1010
6106\sim 10 2×1052\times 10^5