← 返回题目列表

AtCoder · joig2024_e

E. 姓名

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI 君和 IOI 君决定养狗。首先要做的事情是决定狗的名字。经过两人的讨论,决定让狗的名字满足以下条件。 4 满足以下条件。

条件 1 名字由英文字母大写(A, B, ..., Z)和英文字母小写(a, b, ..., z)组成的字符串。

条件 2 JOI 君喜欢的字符串长度为 N 的字符串 S ,所以S 作为名字的子序列。

条件 3 IOI 君喜欢的字符串长度 M 的字符串 T ,所以T 作为名字的子序列。

条件 4 为了让名字更容易被叫出,同样的字符之间应有至少其他字符 K 个以上。严格来说,对于位置不同的每个相同字符, 2 必须在其之间至少有其他字符 K 个以上。需要注意的是,K = 0 的情况或者名字的字符全部不同的情况,也被认为满足这个条件。

但是,这些条件中英语大写字母和小写字母是有区别的。例如 A 和 按字典顺序比较 a 被视为不同的字符,需要注意。

这里,名字的子序列是指可以从名字中去掉某些字符(0 个字符也可以)后得到的字符串。例如,如果名字是 algorithm 时,ai 呀 请注意,它可能是 lgtm 是名字的子序列,但joi 呀 请注意,它可能是 logarithm 不是名字的子序列。

两个人认为名字越短越好,因此,4 在以下条件下决定赋予最短的名字。

给定 JOI 君和 IOI 君喜欢的字符串及整数 K ,请编写一个程序来求狗的名字的字符数。

制約

  • 1 \leqq N \leqq 500.
  • 1 \leqq M \leqq 500.
  • 0 \leqq K \leqq 3.
  • S 是由英文字母大小写组成的长度 N 的字符串。
  • T 是由英文字母大小写组成的长度 M 的字符串。
  • N, M, K 是整数。

小課題

  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 \leqq 25,M \leqq 25.
  6. (15 点) K = 1.
  7. (20 点) K \leqq 2.
  8. (10 点)没有额外的限制。

入力

输入按以下格式给出。

N M K
S
T

出力

狗的名字的字符数 1 请以行的形式输出。


入力例 1

10 10 0
hottokeiki
hottokeiki

出力例 1

10

JOI 君和 IOI 君喜欢的字符串都是 hottokeiki 。这里考虑将狗的名字设为 hottokeiki 。它满足以下 4 条件。

  • 条件 1: 名字由英文字母大小写组成。
  • 条件 2: 文字列 S (hottokeiki) 是狗的名字 hottokeiki 的子序列。
  • 条件 3: 文字列 T (hottokeiki) 是狗的名字 hottokeiki 的子序列。
  • 条件 4: K = 0 因此,这个条件得以满足。

此外,这 4 是满足条件中最短的名字。这些字符数 10 。 你只需要砍掉

此输入示例是一个小作业。 1, 3, 4, 7, 8 满足约束。


入力例 2

10 10 1
hottokeiki
hottokeiki

出力例 2

11

入力例 1 是什么? 表示 K 的值不同。

如果将狗的名字作为输入例 1 相同 hottokeiki ,条件 4 就不满足条件。原因是2 在 t 之间的字符 1 个都没有。

4 作为满足条件的最短名字,可以考虑 hotNtokeiki 等。因为它只有 11 。 你只需要砍掉

此输入示例是一个小作业。 2, 3, 5, 6, 7, 8 满足约束。


入力例 3

10 10 3
hottokeiki
hottokeiki

出力例 3

15

入力例 1, 2 是什么? 表示 K 的值不同。

如果将狗的名字作为输入例 2 相同 hotNtokeiki ,条件 4 就不满足条件。原因是2 在 t 期间 1 个字符,2 在 k 期间 2 个字符,2 在 i 期间 1 个字符。

4 作为满足条件的最短名字,可以考虑 hotarutokeiyuki 等。因为它只有 15 。 你只需要砍掉

此输入示例是一个小作业。 3, 8 满足约束。


入力例 4

6 9 0
Jouhou
Orinpikku

出力例 4

14

JOI君喜欢的字符串是 Jouhou,IOI君喜欢的字符串是 Orinpikku 。这里考虑将狗的名字设为 OJouhorinpikku 。它满足以下 4 条件。

  • 条件 1: 名字由英文字母大小写组成。
  • 条件 2: 文字列 S (Jouhou) 是狗的名字 OJouhorinpikku 的子序列。
  • 条件 3: 文字列 T (Orinpikku) 是狗的名字 OJouhorinpikku 的子序列。
  • 条件 4: K = 0 因此,这个条件得以满足。

此外,这 4 是满足条件中最短的名字之一。输出该字符数 14 。此外,由于区分英文字母的大写和小写,jouhorinpikku(文字数 13等不满足条件。

此输入示例是一个小作业。 4, 7, 8 满足约束。


入力例 5

9 7 1
CoMMiTTee
TeRRaCe

出力例 5

15

4 作为满足条件的最短名字,可以考虑 CoMaMiTeRTeRaCe 等。因为它只有 15 。 你只需要砍掉

此输入示例是一个小作业。 5, 6, 7, 8 满足约束。


入力例 6

6 8 2
JOIIOI
JOIGEGOI

出力例 6

9

4 满足以下条件的最短名称是 JOIGEIGOI 。这个字符数 9 。 你只需要砍掉

此输入示例是一个小作业。 7, 8 满足约束。