# #278. CS240 project Problem 2

# CS240 project Problem 2

# Problem Statement

You are presented with two primary strings: `S`

and `T`

, and a target string `X`

of the same length as `S`

, initially filled entirely with the character `#`

. Your task is to determine if it's possible to transform `X`

into `S`

by repeatedly overlaying the string `T`

onto `X`

.

## Constraints

- The string
`S`

is composed of letters and has a length`N`

. - The string
`T`

also consists of letters and has a length`M`

, where`M`

is less than or equal to`N`

. `X`

is a string of length`N`

filled entirely with the character`#`

.- You can overlay
`T`

on any part of`X`

, replacing`M`

consecutive characters, as many times as you want. - Given lengths: $1 ≤ N ≤ 2×10^5$ and $1 ≤ M ≤ min(N, 5)$.

## Input

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

```
N M
S
T
```

## Output

Print `Yes`

if it is possible to make **X** match **S**; print `No`

otherwise.

### Sample Input 1

```
5 3
ABCBC
ABC
```

### Sample Output 1

```
Yes
```

Below, let $X[l:r]$ denote the part from the $l$-th through the $r$-th character of $X$.

You can make $X$ match $S$ by operating as follows.

- Replace $X[3:5]$ with $T$. $X$ becomes
`##ABC`

. - Replace $X[1:3]$ with $T$. $X$ becomes
`ABCBC`

.

### Sample Input 2

```
7 3
ABBCABC
ABC
```

### Sample Output 2

```
No
```

it's impossible to make $X$ match $S$.

### Sample Input 3

```
12 2
XYXXYXXYYYXY
XY
```

### Sample Output 3

```
Yes
```

# Related

In following contests: