Problem Description

Little A has a string \( t \). He can perform the following operation: cut off a prefix or suffix of \( t \), such that the cut part is a substring of \( t \) after the cut. Little A wants to obtain the string \( s \). Please问他最少需要进行多少次操作。 If it is not possible, output \(-1\).

Input Format

Two lines of strings representing \( t \) and \( s \), respectively.

Output Format

A single integer on one line, representing the answer.

Sample Input and Output

Sample Input #1

abbabb
ba

Sample Output #1

3

Sample Input #2

fxofoxxooffoxooo
fox

Sample Output #2

8

Sample Input #3

abcdefghijklmnopq
rstuvwxyzz

Sample Output #3

-1

Sample Input #4

ycxcy
cxy

Sample Output #4

-1

Notes

Sample Explanation

Sample 1: \(\texttt{abbabb} \to \texttt{abba} \to \texttt{bba} \to \texttt{ba}\). There are multiple solutions.

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}\). There are multiple solutions.

Data Range and Constraints

This problem uses batched testing.

• Subtask 1 (1 point): \( 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 \), data is random.
• Subtask 7 (25 points): No additional constraints.

For \( 100\% \) of the data: \( 1 \leq |s| \leq |t| \leq 5 \times 10^3 \), the character set is \(\in [\texttt{a, z}]\).

Random data: \( s \) and \( t \) characters are random, the character set is \(\in [\texttt{a, c}]\).

Please pay attention to constant optimization.

Problem Source

Sweet Round 05 E.
idea & solution: Isaunoya & Alex_Wei.

见题面 Input 部分

见题面 Output 部分