/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
この問題は F 問題 (Operate K) の部分問題であり、 K=1 です。
F 問題に正解するコードをこの問題に提出することで、この問題に正解できます。
文字列 S に対して以下の操作を 0 回以上 K 回以下行って、文字列 T と一致させられるか判定してください。
- 次の 3 種類の操作のうちひとつを選択し、実行する。
- S 中の (先頭や末尾を含む) 任意の位置に、任意の文字を 1 つ挿入する。
- S 中の文字を 1 つ選び、削除する。
- S 中の文字を 1 つ選び、別の 1 つの文字に変更する。
制約
- S,T は英小文字からなる長さ 1 以上 500000 以下の文字列
- \color{red}{K=1}
入力
入力は以下の形式で標準入力から与えられる。
K S T
出力
K 回以下の操作で S を T に一致させられる時 Yes 、そうでない時 No と出力せよ。
入力例 1
1 abc agc
出力例 1
Yes
abc の 2 文字目の b を g に置き換えることで、 abc を 1 回の操作で agc に変換できます。
入力例 2
1 abc awtf
出力例 2
No
1 回の操作では abc を awtf に変換できません。
入力例 3
1 abc ac
出力例 3
Yes
abc の 2 文字目の b を削除することで、 abc を 1 回の操作で ac に変換できます。
入力例 4
1 back black
出力例 4
Yes
back の 1 文字目と 2 文字目の間に l を挿入することで、 back を 1 回の操作で black に変換できます。
入力例 5
1 same same
出力例 5
Yes
初めから S=T である場合もあります。
入力例 6
1 leap read
出力例 6
No
Score : 350 points
Problem Statement
This problem is a sub-problem of Problem F (Operate K), with K=1.
You can solve this problem by submitting a correct solution for Problem F to this problem.
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.
- \color{red}{K=1}
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
1 abc agc
Sample Output 1
Yes
Replacing the second character b of abc with g converts abc to agc in one operation.
Sample Input 2
1 abc awtf
Sample Output 2
No
abc cannot be converted to awtf in one operation.
Sample Input 3
1 abc ac
Sample Output 3
Yes
Deleting the second character b of abc converts abc to ac in one operation.
Sample Input 4
1 back black
Sample Output 4
Yes
Inserting l between the first and second characters of back converts back to black in one operation.
Sample Input 5
1 same same
Sample Output 5
Yes
It is also possible that S = T from the beginning.
Sample Input 6
1 leap read
Sample Output 6
No