题目描述

小 A 有一个字符串 $t$。他可以进行以下操作：切掉 $t$ 的一个前/后缀，满足切掉的前/后缀为切割后 $t$ 的子串。小 A 想得到字符串 $s$，请问他最少需要进行多少次操作。无解输出 $-1$。

输入格式

两行字符串分别表示 $t,s$。

输出格式

一行一个整数，表示答案。

abbabb
ba

3

fxofoxxooffoxooo
fox

8

abcdefghijklmnopq
rstuvwxyzz

-1

ycxcy
cxy

-1

提示

「样例说明」

样例 $1$：$\texttt{abbabb}\to \texttt{abba}\to \texttt{bba}\to \texttt{ba}$。方案不唯一。

样例 $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}$。方案不唯一。

「数据范围与约定」

本题采用捆绑测试。

• Subtask 1（1 points）：$s=t$。
• Subtask 2（9 points）：$s$ 仅包含字母 $\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$，*数据随机。
• Subtask 7（25 points）：无特殊限制。

对于 $100\%$ 的数据：$1 \leq |s| \leq |t| \leq 5\times 10^3$，字符集 $\in[\texttt{a,z}]$。

*数据随机：$s,t$ 字符均随机，字符集 $\in[\texttt{a,c}]$。

请注意常数优化。

「题目来源」

Sweet Round 05 E。
idea & solution：Isaunoya & Alex_Wei。