SP2325 STRDIST - String Distance

给定两个字符串 $A = a_1 a_2 \ldots a_k$ 和 $B = b_1 b_2 \ldots b_l$，它们的长度分别为 $k$ 和 $l$。我们定义字符串 $A$ 和 $B$ 的距离如下： 定义 $d[i, j]$ 为子串 $a_1 \ldots a_i$ 和 $b_1 \ldots b_j$ 的距离，其中 $0 \le i \le k$，$0 \le j \le l$。这里 $i$ 或 $j$ 为 $0$ 表示空子串。初始条件为 $d[0, 0] = 0$。对于其他 $(i, j) \neq (0, 0)$ 的情况，$d[i, j]$ 为以下表达式中适用的最小值： - 当 $j > 0$ 时，$d[i, j - 1] + 1$ - 当 $i > 0$ 时，$d[i - 1, j] + 1$ - 当 $i > 0$ 且 $j > 0$，并且 $a_i = b_j$ 时，$d[i - 1, j - 1]$ - 当 $i > 0$ 且 $j > 0$，但 $a_i \neq b_j$ 时，$d[i - 1, j - 1] + 1$ - 当 $i \ge 2$ 且 $j \ge 2$，并且 $a_i = b_{j-1}$ 且 $a_{i-1} = b_j$ 时，$d[i - 2, j - 2] + 1$ 字符串 $A$ 和 $B$ 的最终距离为 $d[k, l]$。 给定字符串 $A$ 和 $B$，请计算它们的距离。已知这个距离不会超过 100。

第一行包含两个整数 $k$ 和 $l$，表示字符串 $A$ 和 $B$ 的长度（$1 \le k, l \le 10^5$）。接下来的两行分别给出字符串 $A$ 和 $B$。字符串中只包含小写英文字母。

输出一行，表示字符串 $A$ 和 $B$ 的距离。 **本翻译由 AI 自动生成**