#PQJ730x1001. QOJ 730_1001

    ID: 3026 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:BJOI 2020字符串后缀数组二分答案

QOJ 730_1001

给出只包含小写字母 𝑎 , 𝑏 的两个字符串 𝑠 , 𝑡 , 𝑞 次询问,每次询问 𝑠 [ 𝑙 … 𝑟 ] 和 𝑡 的最长公共子串长度。

输入格式

输入共 𝑞 + 3 行。

第一行一个字符串 𝑠 。

第二行一个字符串 𝑡 。

第三行一个整数 𝑞 。

接下来的 𝑞 行,每行两个整数 𝑙 𝑖 , 𝑟 𝑖 ( 1 ≤ 𝑙 𝑖 ≤ 𝑟 𝑖 ≤ | 𝑠 | ) ,表示一次询问。

输出格式

输出共 𝑞 行。

第 𝑖 行表示 𝑠 [ 𝑙 𝑖 … 𝑟 𝑖 ] 和 𝑡 的最长公共子串长度。

样例数据 Input aaba aaaabbbaa 3 1 4 1 3 2 4 Output 3 3 2 子任务 测试点编号 | 𝑠 | , | 𝑡 | ≤

𝑞 ≤

1

50

50

2 , 3

2 × 10 3

2 × 10 3

4 , 5

2 × 10 5

10

6 ∼ 10

2 × 10 5

2 × 10 5