配点: 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 是整数。
小課題
- (2 点) S = T,K = 0.
- (7 点) S = T,K = 1.
- (16 点) S = T.
- (17 点) K = 0.
- (13 点) K = 1,N \leqq 25,M \leqq 25.
- (15 点) K = 1.
- (20 点) K \leqq 2.
- (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 满足约束。