String Transformation

4

4 votes
Dynamic Programming, 2D dynamic programming, Algorithms
Problem

It is known that the string s contains only lowercase English characters. Also, the string t contains lowercase English characters and digit characters. You can replace each digit character of t by a substring consisting of lowercase English characters. Note that the length of such a substring should be not greater than the digit value.

For example, if string t = “a22fg”, then you can replace the two “2”’s by “bc” and “de”, respectively. So t can be transformed into “abcdefg”. 

Determine if the string t can be transformed into the string s or not.

Note

The lengths of the string s and t are n and m, respectively.

Constraints

  • 1T1000
  • 1n1000
  • 1m1000

Input Format

  • The first line contains a single integer T —- the number of test cases.
  • For each testcase:
    • The first line contains two integers n, m —- the lengths of s and t, respectively.

    • The second line contains a string s of length n.

    • The third line contains a string t of length m.

Output Format

  • For each Testcase, output "YES" if the string t can be transformed into the string s. Otherwise, output "NO".

 

Sample Input
2
4 1
abcd
9
4 3
abcd
ac9
Sample Output
YES
NO
Time Limit: 2.5
Memory Limit: 256
Source Limit:
Explanation

In the first testcase, you can replace the digit character "9" of t by "abcd", because the length of "abcd" is less than 9.

In the second testcase, there is no way to transform the string t into s.

Editor Image

?