19443번 - La Vie En Rose 다국어

Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string $p = p_{1} p_{2} \ldots p_{m}$. So, he wants to generate as many pattern strings as possible from $p$ using the following method: 

1. select some indices $i_1, i_2, \ldots, i_k$ such that $1 \le i_1 < i_2 < \ldots < i_k < |p|$ and $|i_{j} - i_{j + 1}| > 1$ for all $1 \le j < k$.
2. swap $p_{i_{j}}$ and $p_{i_{j} + 1}$ for all $1 \le j \le k$.

Now, for a given a string $s = s_{1} s_{2} \ldots s_{n}$, Professor Zhang wants to find all occurrences of all the generated patterns in $s$.

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le \min (50\,000, n)$): the lengths of $s$ and $p$, respectively.

The second line contains the string $s$, and the third line contains the string $p$. Both strings consist only of lowercase English letters.

Output a binary string of length $n$. The $i$-th character must be '1' if and only if the substring $s_{i} s_{i+1} \ldots s_{i+m-1}$ is one of the generated patterns. Otherwise, the character must be '0'.