子序列

题目描述

给定两个由小写英文字母组成的字符串 $s, t$。请判断是否存在满足以下条件的整数 $i$（$1 \leq i \leq 10^{100} \times |s|$），如果存在则求出这样的 $i$ 的最小值。

• 设把 $s$ 连接 $10^{100}$ 次得到的字符串为 $s'$。要求 $t$ 是字符串 ${s'}_1{s'}_2\ldots{s'}_i$（$s'$ 的前 $i$ 个字符）的子序列。

输入格式

输入按以下格式从标准输入给出：

$s$
$t$

输出格式

如果存在满足条件的整数 $i$，输出其最小值；如果不存在，输出 -1。

样例

contest
son

10

因为 $t =$ son 是字符串 contestcon（$s' =$ contestcontestcontest... 的前 $10$ 个字符）的子序列，所以 $i = 10$ 满足条件。

另一方面，$t$ 不是字符串 contestco（$s'$ 的前 $9$ 个字符）的子序列，所以 $i = 9$ 不满足条件。

同理，任何不超过 $8$ 的整数也都不满足条件。因此，满足条件的整数 $i$ 的最小值为 $10$。

contest
programming

-1

$t =$ programming 不是 $s' =$ contestcontestcontest... 的子序列。因此，不存在满足条件的整数 $i$。

contest
sentence

33

这里无法给出这样的用例，但请注意答案可能不满足 $32$ 位整数的范围。

数据范围

• $1 \leq |s| \leq 10^5$
• $1 \leq |t| \leq 10^5$
• $s, t$ 由小写英文字母组成

提示

• 字符串 $a$ 的子序列是指：从 $a$ 中删除 $0$ 个以上字符后，将剩余字符按相对顺序不变地连接起来得到的字符串。例如，contest 的子序列有 net、c、contest 等。