33647번 - 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≥0$ we let $s^k$ denote the result of concatenating $k$ copies of $s,ドル i.e. ab$^3=$ababab. If $k=0,ドル then $s^k$ is just the empty string.

Finally, a collection of nonempty strings $s_1,\dots ,s_k$ is said to partition a string $s$ if $s=s_1+s_2+\dots +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,\dots ,s_k$ of $s$ and integers $a_1,a_2,\dots ,a_k≥0$ such that $t=s_1^{a_1}+s_2^{a_2}+\dots +s_k^{a_k}$.

입력

The first line of input contains two integers $N$ (1ドル≤N≤300$) and $M$ (1ドル≤M≤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 yes if it there is a partition $s_1,s_2,\dots ,s_k$ of $s$ and integers $a_1,a_2,\dots ,a_k≥0$ such that $t=s_1^{a_1}+s_2^{a_2}+\dots +s_k^{a_k},ドル otherwise output no.

제한

힌트