题目描述

给你两个由小写英文字母组成的字符串 $S$ 和 $T$ 。

求最小正整数 $k$ ，使得你可以选择 $S$ 的 $k$ 前缀（不一定是不同的），使它们的连接与 $T$ 重合。

换句话说，找出最小的正整数 $k$ ，使得在 $1$ 和 $|S|$ 之间存在一个由整数组成的 $k$ 元组 $(a_1,a_2,\ldots, a_k)$ ，使得 $T=S_{a_1}+S_{a_2}+\cdots +S_{a_k}$ ，其中 $S_i$ 表示 $S$ 从 $1$ 个字符到 $i$ 个字符的子串，而 $+$ 表示字符串的连接。

如果无法使其与 $T$ 重合，则打印 $-1$ 代替。

输入格式

第一行输入字符串 $S$

第二行输入字符串 $T$

输出格式

打印最小的正整数 $k$ ，以便选择 $S$ 的 $k$ 个前缀，使它们的连接与 $T$ 重合。不可能与 $T$ 重合，请打印 $-1$ 。

aba
ababaab

3

atcoder
ac

-1

样例 1 解释

$T=$ ababaab 可以写成 ab + aba + ab，其中 ab 和 aba 是 $S=$ aba 的前缀。

由于无法用两个或更少的 aba 前缀来表达 ababa，因此打印 $3$ 。

提示

• $1\ \leq\ |S|\ \leq\ 5\times\ 10^5$
• $1\ \leq\ |T|\ \leq\ 5\times\ 10^5$
• $S,T$ 仅由小写字母构成