P9109 [PA 2020] Tekstówka

**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 4 [Tekstówka](https://sio2.mimuw.edu.pl/c/pa-2020-1/tek/)** 在去年我们在某社交网络的粉丝页上进行的 PA 中，参与者大声地问我们：「题呢？」。今年，我们决定满足您的期望。 给出了由英文小写字母组成的字符串 $s$ 和 $t$。令 $s_{i,j}\ (1\le i\le j\le |s|)$ 表示由 $s$ 的第 $i$ 个到第 $j$ 个（包含两端）字符依次组成的子串。我们也同样定义 $t_{i,j}$。 你的任务是处理 $q$ 次查询。每次查询用四个整数 $i,j,k,l$ 表示，这里 $1\le i\le j\le |s|,1\le k\le l\le |t|$。对于每次查询，你需要输出子串 $s_{i,j}$ 和子串 $t_{k,l}$ 的最长公共子序列。 注：一个字符串的子序列是指一个字符串通过删除一些（可能不删除）字符且不改变剩余字符顺序得到的串。例如，$\texttt{potyczki}$ 的子串可以是 $\texttt{tyki}$ 或 $\texttt{pi}$，但不能是 $\texttt{koty}$。 我们称字符串 $a$ 和 $b$ 的公共子序列为既是 $a$ 的子序列，又是 $b$ 的子序列的子序列。 我们称字符串 $a$ 和 $b$ 的最长公共子序列为 $a$ 和 $b$ 的子序列中最长的一个。

输入第一行包含三个整数 $n,m,q$，分别表示 $s$ 串和 $t$ 串的长度与询问次数。 第二行包含一个由小写英文字母组成且长为 $n$ 的字符串 $s$。 第三行包含一个由小写英文字母组成且长为 $m$ 的字符串 $t$。 接下来 $q$ 行，每行四个整数 $i,j,k,l$，意义如题目描述。

输出 $q$ 行，每行一个整数，表示对询问的回答。

#### 数据范围 **本题采用捆绑测试** - 对于一些子任务，满足 $n,m,q\le 600$； - 对于一些其他的子任务，满足 $n,m\le 600$； - 对于一些其他的子任务，满足 $q\le 5\times 10^3$。 对于上述情况，至少有一个子任务满足。 对于 $100\%$ 的数据，保证 $1\le n,m\le 3\times 10^3$，$1\le q\le 10^5$，$1\le i\le j\le n$，$1\le k\le l\le m$。