当前没有测试数据。

G - 前缀拼接

得分：600分

题目描述

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

找到最小的正整数$k$，使得你可以选择$S$的$k$个前缀，拼接它们后得到$T$。

换句话说，找到最小的正整数$k$，使得存在一个$k$元组$(a_1,a_2,\ldots, a_k)$，其中$a_i$是位于1到$|S|$之间的整数，满足
$T=S_{a_1}+S_{a_2}+\cdots +S_{a_k}$， 这里$S_i$表示从$S$的第1个字符到第$i$个字符的子串，$+$表示字符串的拼接。

如果不能得到和$T$相同的结果，输出$-1$。

约束条件

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

输入

输入的格式如下：

$S$

$T$

输出

输出最小的正整数$k$，使得你可以选择$S$的$k$个前缀，拼接它们后得到$T$。 如果不能得到和$T$相同的结果，输出$-1$。

aba
ababaab

3

$T=$ ababaab 可以被写成 ab + aba + ab，其中ab和aba是$S=$ aba的前缀。
因为不能使用少于或等于两个aba的前缀来表示 ababaab，所以输出$3$。

atcoder
ac

-1

由于无法用$S$的前缀拼接成$T$，所以输出$-1$。