AT_joig2024_e 名前 (Name)

JOI 君和 IOI 君决定养一只狗。首先要做的事情是给狗取一个名字。经过两人的商议，决定名字需要满足以下 $4$ 个条件。 > **条件 1** 名字必须是由英文字母大写字母（`A`, `B`, ..., `Z`）和小写字母（`a`, `b`, ..., `z`）组成的字符串。 > > **条件 2** JOI 君喜欢的字符串是长为 $N$ 的字符串 $S$，因此 $S$ 必须作为名字的一个子序列出现。 > > **条件 3** IOI 君喜欢的字符串是长为 $M$ 的字符串 $T$，因此 $T$ 必须作为名字的一个子序列出现。 > > **条件 4** 为了使名字读起来方便，对于名字中任意两个相同的字符，其间必须至少有 $K$ 个其他字符。严格来说，对于任意位置不同但字符相同的两个字母，它们之间必须有至少 $K$ 个不同的字符。注意，如果 $K=0$，或者名字中的字母全部互不相同，则此条件自动满足。 > > 需要注意的是，英文字母的大写和小写是有区分的。例如，`A` 和 `a` 被认为是不同的字母。 这里，名字的子序列表示从名字中删除若干（可以是 $0$ ）个字符后得到的字符串。例如，当名字为 `algorithm` 时，`ai` 和 `lgtm` 是该名字的子序列，但 `joi` 和 `logarithm` 不是。 两人认为名字越短越好，所以请在上述 $4$ 条件下，为狗狗取一个最短的名字。 给定 JOI 君和 IOI 君喜欢的字符串，以及整数 $K$，请你编写程序输出名字的最小长度。

输入按以下格式给出。 > $N$ $M$ $K$ $S$ $T$

请输出满足条件的名字的最小长度，仅一行。

## 子任务 1. （$2$ 分）$S = T$，$K = 0$。 2. （$7$ 分）$S = T$，$K = 1$。 3. （$16$ 分）$S = T$。 4. （$17$ 分）$K = 0$。 5. （$13$ 分）$K = 1$，$N \leq 25$，$M \leq 25$。 6. （$15$ 分）$K = 1$。 7. （$20$ 分）$K \leq 2$。 8. （$10$ 分）无其它额外限制。 ## 样例解释 1 JOI 君和 IOI 君喜欢的字符串都是 `hottokeiki`。如果把狗的名字取为 `hottokeiki`，那么： - **条件 1：** 名字由大小写英文字母构成。 - **条件 2：** 字符串 $S$（`hottokeiki`）是名字 `hottokeiki` 的子序列。 - **条件 3：** 字符串 $T$（`hottokeiki`）是名字 `hottokeiki` 的子序列。 - **条件 4：** $K=0$，所以条件自动满足。 这是满足所有条件的最短名字，其长度为 $10$。 这个输入满足子任务 $1,3,4,7,8$ 的限制。 ## 样例解释 2 本例和样例 1 的区别只是 $K$ 的取值不同。 如果名字还是取为 `hottokeiki`，则**条件 4**不满足，因为两个 `t` 中间没有 $1$ 个字符。 满足所有条件的最短名字可以是 `hotNtokeiki`，长度为 $11$。 这个输入满足子任务 $2,3,5,6,7,8$ 的限制。 ## 样例解释 3 本例和样例 1,2 的区别是 $K$ 的取值不同。 如果名字用 `hotNtokeiki`，则**条件 4**不满足，因为两个 `t` 之间仅隔 $1$ 个字符，两个 `k` 之间只有 $2$ 个字符，以及两个 `i` 之间仅有 $1$ 个字符。 满足所有条件的最短名字可以是 `hotarutokeiyuki`，长度为 $15$。 这个输入满足子任务 $3,8$ 的限制。 ## 样例解释 4 JOI 君喜欢的字符串为 `Jouhou`，IOI 君喜欢的字符串为 `Orinpikku`。如果将狗的名字取为 `OJouhorinpikku`，那么： - **条件 1：** 名字由大小写英文字母构成。 - **条件 2：** 字符串 $S$（`Jouhou`）是名字 `OJouhorinpikku` 的子序列。 - **条件 3：** 字符串 $T$（`Orinpikku`）是名字 `OJouhorinpikku` 的子序列。 - **条件 4：** $K=0$，所以条件自动满足。 这是一个满足所有条件的最短名字之一，长度为 $14$。注意，因为大小写有区分，`jouhorinpikku`（长度 $13$）等名字并不满足条件。 这个输入满足子任务 $4,7,8$ 的限制。 ## 样例解释 5 满足所有条件的最短名字之一是 `CoMaMiTeRTeRaCe`，长度为 $15$。 这个输入满足子任务 $5,6,7,8$ 的限制。 ## 样例解释 6 满足所有条件的最短名字是 `JOIGEIGOI`，长度为 $9$。 这个输入满足子任务 $7,8$ 的限制。 # 数据范围与约定 - $1 \leq N \leq 500$。 - $1 \leq M \leq 500$。 - $0 \leq K \leq 3$。 - $S$ 是长度为 $N$ 的仅包含大小写英文字母的字符串。 - $T$ 是长度为 $M$ 的仅包含大小写英文字母的字符串。 - $N, M, K$ 均为整数。 由 ChatGPT 5 翻译