| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 36 | 15 | 10 | 55.556% |
Given a string of even length $s = s_1 \ldots s_n$, we define $\mathrm{shuffle}$ operation which transforms a string into a new string according to the following rule:
$$\mathrm{shuffle}(s) = s_1 s_3 \ldots s_{n-1} s_2 s_4 \ldots s_n$$
For example, $\mathrm{shuffle}(\texttt{abcdef}) = \texttt{acebdf}$.
You are given two strings of equal even length, $s$ and $t$. How many times do you have to apply shuffle operation to $s$ in order to get $t$ as a result?
In the other words, find minimum $k$ such that $\underbrace{\mathrm{shuffle}(\mathrm{shuffle}(\dots \mathrm{shuffle}}_{k\ \mathrm{times}} (s)\dots)) = t$ or report that it is not possible to reach $t$ in any number of operations.
The first line of input contains a string $s$, the second contains a string $t$ ($|s| = |t|$, $2 \leq |s| \leq 10^6$, $|s|$ is even). Both strings consist of lowercase English characters.
Print minimum non-negative $k$ such that it is possible to obtain $t$ from $s$ by applying shuffle operation $k$ times (or maybe not applying at all if $k = 0$), or print -1 if it is impossible.
abcdef aedcbf
2
petrozavodsk poztsvoedark
3
qwerty ytrewq
-1