Problem Description

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$.

Input Format

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

Output Format

Output one integer in one line, representing the answer.

abbabb
ba

3

fxofoxxooffoxooo
fox

8

abcdefghijklmnopq
rstuvwxyzz

-1

ycxcy
cxy

-1

Hint

"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 E。
idea & solution: Isaunoya & Alex_Wei。

Translated by ChatGPT 5