← 返回题目列表

Codeforces · 1409/F

F. 长度为 2 的子序列

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

给定两个由小写拉丁字母组成的字符串 $$$s$$$ 和 $$$t$$$。 $$$t$$$ 的长度为 $$$2$$$ (即该字符串仅包含两个字符)。

一步操作中,您可以选择$$$s$$$中的任意字符并将其替换为任意小写拉丁字母。更正式地说,您选择一些 $$$i$$$ 并将 $$$s_i$$$ (位于 $$$i$$$ 位置的字符)替换为从 'a' 到 'z' 的某个字符。

您希望进行不超过 $$$k$$$ 的替换,以最大化 $$$t$$$ 作为子序列在 $$$s$$$ 中出现的次数。

回想一下,子序列是可以通过删除零个或多个元素而不改变剩余元素的顺序从给定序列派生的序列。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 200$$$; $$$0 \le k \le n$$$) — $$$s$$$ 的长度和你可以进行的最大移动次数。输入的第二行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。输入的第三行包含由两个小写拉丁字母组成的字符串 $$$t$$$。

输出

打印一个整数 — 如果您在 $$$s$$$ 中替换不超过 $$$k$$$ 个字符,那么 $$$t$$$ 在 $$$s$$$ 中作为子序列出现的最大可能次数。

示例

输入 #1

4 2
bbaa
ab

输出 #1

3

输入 #2

7 3
asddsaf
sd

输出 #2

10

输入 #3

15 6
qwertyhgfdsazxc
qa

输出 #3

16

输入#4

7 2
abacaba
aa

输出#4

15

注意

在第一个示例中,您可以通过将 $$$s_1$$$ 替换为 'a' 并将 $$$s_4$$$ 替换为 'b' 来获取字符串“abab”。那么答案是$$$3$$$。

在第二个示例中,您可以获取字符串“ssddsdd”并得到答案$$$10$$$。

第四个例子中,获取字符串“aaacaaa”,得到答案$$$15$$$。