| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 32 | 12 | 12 | 37.500% |
Finn is playing a game of "Flip it and Stick it" which is abbreviated as FiSi. FiSi is a one-player game played on two strings, $S$ and $T,ドル of 0s and 1s. Finn is allowed to make moves of the following form:
For example, Finn may take the string $S =$ 101100, take the substring 011 starting at index 2ドル$ (assuming 1ドル$-based string indexing), and create the string $S =$ 111000 in one move. Finn wins the game if $S$ does not contain $T$ as a substring. Your task is to help Finn determine the length of the shortest winning sequence of moves or tell him that the game cannot be won.
The first line of input contains the string $S$ $(1 \le |S| \le 200,000円)$.
The second line of input contains the string $T$ $(1 \le |T| \le 3)$.
In the table below, $T_1$ is the first bit in $T,ドル $T_2$ is the second bit in $T,ドル and $T_3$ is the third bit in $T,ドル when reading from left-to-right.
Output the minimum number of moves needed or -1 if it is impossible to win the game.
100110 10
2
Finn starts with the string 100110. He cannot avoid 10 as a substring in one move, but he can in two moves.
For example, his first move could be to reverse the substring from index 4ドル$ to index 6ドル$ (110) to get 100011. Then, his second move can be to reverse the substring from index 1ドル$ to index 4ドル$ (1000) to get 000111, which does not have 10 as a substring.
000 00
-1
No matter how many moves Finn makes, the string $S$ will always contain $T$ as a substring.