/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
英小文字からなる文字列 S, T が与えられます。あなたは S の文字を一つ選んで好きな英小文字に書き換えることを 0 回以上 K 回以下行うことができます。
S を書き換えたあと、S の部分列かつ T の部分列であるような文字列のうち、最長のものの長さは最大で何文字になりますか？
ただし、文字列 x が文字列 y の部分列であるとは、y から 0 個以上の文字を取り除き、残りの文字を元の順序で連結することで x が得られることをいいます。
制約
- 1 \leq |S|, |T| \leq 1000
- 1 \leq K \leq 10
- S, T は英小文字からなる。
入力
入力は以下の形式で標準入力から与えられる。
S T K
出力
答えを出力せよ。
入力例 1
strength slang 1
出力例 1
4
例えば、S の 3 文字目を l に書き換えることで、 slng が S の部分列かつ T の部分列となります。
長さ 5 以上の文字列が S の部分列かつ T の部分列として現れるようにすることはできないので、4 を出力します。
入力例 2
asdbvaklwebjkalhakslhgweqwbq obqweogkmawgjkoanboebeoqejkazxcnmvqse 10
出力例 2
19
Score : 6 points
Problem Statement
You are given strings S and T consisting of lowercase English letters. You can do the following operation between 0 and K times: choose one of the characters of S and replace it with any lowercase English letter.
What is the length of the longest possible string that is a subsequence of S after the replacements and also a subsequence of T?
Here, a string x is said to be a subsequence of a string y if x can result from removing zero or more characters from y and concatenating the remaining strings without changing the order.
Constraints
- 1 \leq |S|, |T| \leq 1000
- 1 \leq K \leq 10
- S and T consist of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S T K
Output
Print the answer.
Sample Input 1
strength slang 1
Sample Output 1
4
By replacing the 3-rd character of S with l, slng becomes a subsequence of both S and T.
Since it is impossible to have a subsequence of both S and T of length 5 or longer, 4 should be printed.
Sample Input 2
asdbvaklwebjkalhakslhgweqwbq obqweogkmawgjkoanboebeoqejkazxcnmvqse 10
Sample Output 2
19