{"problem":{"name":"[PA 2020] Tekstówka","description":{"content":"**题目译自 [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 中，参与者大声地问我们：「题呢？」。今年，我们决定满足您的期望。 给出了由英文小写字","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":8000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9109"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [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/)**\n\n在去年我们在某社交网络的粉丝页上进行的 PA 中，参与者大声地问我们：「题呢？」。今年，我们决定满足您的期望。\n\n给出了由英文小写字母组成的字符串 $s$ 和 $t$。令 $s_{i,j}\\ (1\\le i\\le j\\le |s|)$ 表示由 $s$ 的第 $i$ 个到第 $j$ 个（包含两端）字符依次组成的子串。我们也同样定义 $t_{i,j}$。\n\n你的任务是处理 $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}$ 的最长公共子序列。\n\n注：一个字符串的子序列是指一个字符串通过删除一些（可能不删除）字符且不改变剩余字符顺序得到的串。例如，$\\texttt{potyczki}$ 的子串可以是 $\\texttt{tyki}$ 或 $\\texttt{pi}$，但不能是 $\\texttt{koty}$。\n\n我们称字符串 $a$ 和 $b$ 的公共子序列为既是 $a$ 的子序列，又是 $b$ 的子序列的子序列。\n\n我们称字符串 $a$ 和 $b$ 的最长公共子序列为 $a$ 和 $b$ 的子序列中最长的一个。\n\n## Input\n\n输入第一行包含三个整数 $n,m,q$，分别表示 $s$ 串和 $t$ 串的长度与询问次数。\n\n第二行包含一个由小写英文字母组成且长为 $n$ 的字符串 $s$。\n\n第三行包含一个由小写英文字母组成且长为 $m$ 的字符串 $t$。\n\n接下来 $q$ 行，每行四个整数 $i,j,k,l$，意义如题目描述。\n\n## Output\n\n输出 $q$ 行，每行一个整数，表示对询问的回答。\n\n[samples]\n\n## Note\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n- 对于一些子任务，满足 $n,m,q\\le 600$；\n- 对于一些其他的子任务，满足 $n,m\\le 600$；\n- 对于一些其他的子任务，满足 $q\\le 5\\times 10^3$。\n\n对于上述情况，至少有一个子任务满足。\n\n对于 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9109","tags":["2020","PA（波兰）"],"sample_group":[["5 6 7\nabaab\nbabbaa\n1 5 1 6\n1 3 2 4\n2 5 2 5\n1 4 2 5\n2 5 3 6\n2 2 5 6\n3 4 2 2","4\n2\n2\n3\n3\n0\n1"]],"created_at":"2026-03-03 11:09:25"}}