P6652 "SWTR-5" String

Little A has a string $t$. He can do the following operation: cut off a prefix or suffix of $t$, with the condition that the removed prefix/suffix is a substring of $t$ **after the cut**. Little A wants to obtain the string $s$. What is the minimum number of operations needed? If it is impossible, output $-1$.

Two lines, each containing a string, representing $t$ and $s$.

Output one integer in one line, representing the answer.

"Sample Explanation" Sample $1$: $\texttt{abbabb}\to \texttt{abba}\to \texttt{bba}\to \texttt{ba}$. The solution is not unique. Sample $2$: $\texttt{fxofoxxooffoxooo}\to\texttt{xofoxxooffoxooo}\to\texttt{foxxooffoxooo}\to\texttt{xooffoxooo}\to\texttt{ffoxooo}\to\texttt{ffoxoo}\to\texttt{ffoxo}\to\texttt{ffox}\to\texttt{fox}$. The solution is not unique. "Constraints and Notes" **This problem uses bundled tests.** - Subtask 1 (1 points): $s=t$. - Subtask 2 (9 points): $s$ contains only the letter $\texttt{a}$. - Subtask 3 (15 points): $|t|\leq 100$. - Subtask 4 (17 points): $|t|\leq 500$. - Subtask 5 (18 points): $|t|\leq 1.5\times 10^3$. - Subtask 6 (15 points): $|s|=4$, *testdata is random. - Subtask 7 (25 points): No special restrictions. For $100\%$ of the testdata: $1 \leq |s| \leq |t| \leq 5\times 10^3$, character set $\in[\texttt{a,z}]$. *Random testdata: the characters of $s,t$ are random, character set $\in[\texttt{a,c}]$. **Please pay attention to constant-factor optimization.** --- "Source" [Sweet Round 05](https://www.luogu.com.cn/contest/28195) E。 idea & solution: [Isaunoya](https://www.luogu.com.cn/user/96580) & [Alex_Wei](https://www.luogu.com.cn/user/123294)。 Translated by ChatGPT 5