Problem H
Power String Matching
For two strings $s_1$ and $s_2$, let $s_1 + s_2$ denote their concatenation, e.g. abc + cda is the string abccda.
Now for a string $s$ and an integer $k \geq 0$ we let $s^ k$ denote the result of concatenating $k$ copies of $s$, i.e. $\texttt{ab}^3 = \texttt{ababab}$. If $k = 0$, then $s^ k$ is just the empty string.
Finally, a collection of nonempty strings $s_1, \ldots , s_ k$ is said to partition a string $s$ if $s = s_1 + s_2 + \ldots + s_ k$.
For this problem, you will be given two strings $s, t$. The goal is to determine if there is a partition $s_1, s_2, \ldots , s_ k$ of $s$ and integers $a_1, a_2, \ldots , a_ k \geq 0$ such that $t = s_1^{a_1} + s_2^{a_2} + \ldots + s_ k^{a_ k}$.
Input
The first line of input contains two integers $N$ ($1 \leq N \leq 300$) and $M$ ($1 \leq M \leq 300$). The second line contains a string $s$ of length $N$ and the third line contains a string $t$ of length $M$. Both strings contain only the characters 0 and 1.
Output
Output yes if it there is a partition $s_1, s_2, \ldots , s_ k$ of $s$ and integers $a_1, a_2, \ldots , a_ k \geq 0$ such that $t = s_1^{a_1} + s_2^{a_2} + \ldots + s_ k^{a_ k}$, otherwise output no.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 5 1100 11010 |
yes |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 2 1100 01 |
no |
| Sample Input 3 | Sample Output 3 |
|---|---|
9 14 010100110 11110101010100 |
yes |
