F - Operate K Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

この問題は C 問題 (Operate 1) を完全に含んでおり、 K \le 20 です。
この問題に正解するコードを C 問題に提出することで、 C 問題に正解できます。

文字列 S に対して以下の操作を 0 回以上 K 回以下行って、文字列 T と一致させられるか判定してください。

  • 次の 3 種類の操作のうちひとつを選択し、実行する。
    • S 中の (先頭や末尾を含む) 任意の位置に、任意の文字を 1 つ挿入する。
    • S 中の文字を 1 つ選び、削除する。
    • S 中の文字を 1 つ選び、別の 1 つの文字に変更する。

制約

  • S,T は英小文字からなる長さ 1 以上 500000 以下の文字列
  • K は \color{red}{1 \le K \le 20} を満たす整数

入力

入力は以下の形式で標準入力から与えられる。

K
S
T

出力

K 回以下の操作で S を T に一致させられる時 Yes 、そうでない時 No と出力せよ。

入力例 1

3
abc
awtf

出力例 1

Yes

例えば、次のように操作することで、 3 回の操作で abc を awtf に変換できます。

  • 2 文字目の b を w に変更する。操作後の文字列は awc となる。
  • 3 文字目の c を f に変更する。操作後の文字列は awf となる。
  • 2 文字目と 3 文字目の間に t を挿入する。操作後の文字列は awtf となる。

入力例 2

2
abc
awtf

出力例 2

No

2 回以下の操作では abc を awtf に変換できません。

入力例 3

17
twothousandtwentyfour
happynewyear

出力例 3

Yes

Score : 525 points

Problem Statement

This problem fully contains Problem C (Operate 1), with K \le 20.
You can solve Problem C by submitting a correct solution to this problem for Problem C.

Determine whether it is possible to perform the following operation on string S between 0 and K times, inclusive, to make it identical to string T.

  • Choose one of the following three operations and execute it.
    • Insert any one character at any position in S (possibly the beginning or end).
    • Delete one character from S.
    • Choose one character in S and replace it with another character.

Constraints

  • Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.
  • K is an integer satisfying \color{red}{1 \le K \le 20}.

Input

The input is given from Standard Input in the following format:

K
S
T

Output

If S can be made identical to T with at most K operations, print Yes; otherwise, print No.

Sample Input 1

3
abc
awtf

Sample Output 1

Yes

For example, here is a way to convert abc to awtf with three operations:

  • Replace the second character b with w. After the operation, the string becomes awc.
  • Replace the third character c with f. After the operation, the string becomes awf.
  • Insert t between the second and third characters. After the operation, the string becomes awtf.

Sample Input 2

2
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf with two or fewer operations.

Sample Input 3

17
twothousandtwentyfour
happynewyear

Sample Output 3

Yes