CF682D Alyona and Strings

Alyona 从森林回来后开始读书。她发现了两个字符串 $s$ 和 $t$，它们的长度分别为 $n$ 和 $m$。按照惯例，阅读让 Alyona 感到无聊，于是她把注意力转移到了这两个非常相似的字符串上。 Alyona 有一个最喜欢的正整数 $k$，由于她年纪尚小，$k$ 不超过 $10$。现在，Alyona 想要从字符串 $s$ 中选择 $k$ 个不相交的非空子串，使得这些子串也作为 $t$ 中的不相交子串出现，并且它们在 $s$ 和 $t$ 中的顺序相同。她还希望这些子串的总长度在所有选择方案中最大。 形式上，Alyona 想要找到一组 $k$ 个非空字符串 $p_{1},p_{2},p_{3},...,p_{k}$，满足以下条件： - $s$ 可以表示为 $a_{1}p_{1}a_{2}p_{2}\ldots a_{k}p_{k}a_{k+1}$ 的拼接，其中 $a_{1},a_{2},...,a_{k+1}$ 是任意字符串（其中有些可以为空）； - $t$ 可以表示为 $b_{1}p_{1}b_{2}p_{2}\ldots b_{k}p_{k}b_{k+1}$ 的拼接，其中 $b_{1},b_{2},...,b_{k+1}$ 是任意字符串（其中有些可以为空）； - 所有 $p_1,p_2,...,p_k$ 的总长度尽可能最大。 请帮助 Alyona 解决这个复杂问题，至少求出这些字符串的最大总长度。 字符串的子串定义为它的某个连续子序列。

第一行输入三个整数 $n$、$m$、$k$（$1 \leq n, m \leq 1000$，$1 \leq k \leq 10$），分别表示字符串 $s$ 的长度、字符串 $t$ 的长度和 Alyona 最喜欢的数字。 第二行输入一个只包含小写英文字母的字符串 $s$。 第三行输入一个只包含小写英文字母的字符串 $t$。

输出一行，一个非负整数，即所选子串的最大总长度。 保证至少存在一种合法的选择方案。

下图描述了第二个样例的答案：  由 ChatGPT 5 翻译