← 返回题目列表

AtCoder · past202206_l

L. 几乎LCS

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

分数: 6 点

问题陈述

给你字符串 S 和 T 由小写英文字母组成。 您可以在之间执行以下操作 0 和 K 次:选择其中一个字符 S 并将其替换为任意小写英文字母。

的子序列的最长可能字符串的长度是多少 S 替换后以及后续的 T?
这里是一个字符串 x 被认为是字符串的子序列 y if x 可能是由于从其中删除零个或多个字符而导致的 y 并连接剩余的字符串而不改变顺序。

约束

  • 1 \leq |S|, |T| \leq 1000
  • 1 \leq K \leq 10
  • S 和 T 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

S
T
K

输出

打印答案。


示例输入 1

strength
slang
1

示例输出 1

4

通过更换 3-rd 字符 S 与 l, slng 成为两者的子序列 S 和 T.

由于不可能同时具有两者的子序列 S 和 T 长度 5 或更长, 4 。


示例输入 2

asdbvaklwebjkalhakslhgweqwbq
obqweogkmawgjkoanboebeoqejkazxcnmvqse
10

示例输出 2

19