前缀-子串 LCS

【题目描述】

给定一个长度为 $M$ 的字符串 $S$ 和一个长度为 $N$ 的字符串 $T$。 依次处理以下 $Q$ 个查询：

• $a$ $b$ $c$：输出 $(S_0, S_1, \dots, S_{a-1})$ 与 $(T_b, T_{b+1}, \dots, T_{c-1})$ 的最长公共子序列的长度。

【输入】

$Q$
$S$
$T$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_{Q-1}$ $b_{Q-1}$ $c_{Q-1}$

【输出】

对每个查询输出一行，表示对应两个序列的最长公共子序列的长度。

【输入样例】

3
abcb
acb
3 0 3
4 1 3
2 1 2

【输出样例】

2
2
0

【数据范围】

• $1 \leq M \leq 1000$
• $1 \leq N \leq 1000$
• $1 \leq Q \leq 500000$
• $0 \leq a_i \leq M$
• $0 \leq b_i \leq c_i \leq N$
• $S$ 和 $T$ 的每个字符均为小写英文字母。

【来源】

Library Checker（yosupo06） prefix_substring_lcs