前缀拼接

题目描述

给定两个由小写英文字母组成的字符串 $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

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

由于用 ababaab 的两个或更少个前缀无法拼出它，输出 3。

atcoder
ac

-1

由于无法用 $S$ 的前缀连接出 $T$，输出 $-1$。

数据范围

• $1 \le |S| \le 5 \times 10^5$
• $1 \le |T| \le 5 \times 10^5$
• $S$ 和 $T$ 是由小写英文字母组成的字符串。