P9109 [PA 2020] Tekstówka

**This problem is translated from [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Round 4 [Tekstówka](https://sio2.mimuw.edu.pl/c/pa-2020-1/tek/).** Last year, during the PA held on a fan page of a certain social network, participants loudly asked us: “Where is the problem?”. This year, we decided to meet your expectations. You are given two strings $s$ and $t$ consisting of lowercase English letters. Let $s_{i,j}\ (1\le i\le j\le |s|)$ denote the substring formed by the $i$-th through the $j$-th characters (inclusive) of $s$ in order. We define $t_{i,j}$ in the same way. Your task is to process $q$ queries. Each query is given by four integers $i, j, k, l$, where $1\le i\le j\le |s|$ and $1\le k\le l\le |t|$. For each query, output the length of the longest common subsequence of the substring $s_{i,j}$ and the substring $t_{k,l}$. Note: A subsequence of a string is a string obtained by deleting some (possibly none) characters without changing the order of the remaining characters. For example, subsequences of $\texttt{potyczki}$ can be $\texttt{tyki}$ or $\texttt{pi}$, but cannot be $\texttt{koty}$. We call a common subsequence of strings $a$ and $b$ a subsequence that is both a subsequence of $a$ and a subsequence of $b$. We call the longest common subsequence of strings $a$ and $b$ the longest one among all common subsequences of $a$ and $b$.

The first line contains three integers $n, m, q$, representing the lengths of strings $s$ and $t$, and the number of queries. The second line contains a string $s$ of length $n$ consisting of lowercase English letters. The third line contains a string $t$ of length $m$ consisting of lowercase English letters. The next $q$ lines each contain four integers $i, j, k, l$, with the meaning as described above.

Output $q$ lines, each containing one integer, the answer to the corresponding query.

#### Constraints **This problem uses bundled testdata.** - For some subtasks, $n, m, q\le 600$. - For some other subtasks, $n, m\le 600$. - For some other subtasks, $q\le 5\times 10^3$. Among the above cases, at least one subtask is satisfied. For $100\%$ of the testdata, it is guaranteed that $1\le n, m\le 3\times 10^3$, $1\le q\le 10^5$, $1\le i\le j\le n$, and $1\le k\le l\le m$. Translated by ChatGPT 5