Strings of Impurity

题目描述

给定两个由小写英文字母组成的字符串 $s$ 和 $t$。判断是否存在满足以下条件的整数 $i$，如果存在，找出最小的这样的 $i$。

令 $s'$ 为将 $s$ 连续重复 $10^{100}$ 次得到的字符串。$t$ 是字符串 ${s'}_1{s'}_2\ldots{s'}_i$（$s'$ 的前 $i$ 个字符）的一个子序列。

输入格式

输入按标准输入给出，格式如下： $s$ $t$

输出格式

如果存在满足以下条件的整数 $i$，输出最小的这样的 $i$；否则，输出 $-1$。

contest
son

10

contest
programming

-1

contest
sentence

33

提示

$1 \leq |s| \leq 10^5$ $1 \leq |t| \leq 10^5$ $s$ 和 $t$ 由小写英文字母组成。字符串 $a$ 的一个子序列是通过从 $a$ 中删除零个或多个字符并按原相对顺序连接剩余字符得到的字符串。例如，$contest$ 的子序列包括 $net$、$c$ 和 $contest$。$t =$ $son$ 是字符串 $contestcon$（$s' =$ $contestcontestcontest...$ 的前 $10$ 个字符）的一个子序列，所以 $i = 10$ 满足条件。另一方面，$t$ 不是字符串 $contestco$（$s'$ 的前 $9$ 个字符）的一个子序列，所以 $i = 9$ 不满足条件。类似地，小于 $9$ 的任何整数也不满足条件。因此，使条件成立的最小整数 $i$ 为 $10$。
$t =$ $programming$ 不是字符串 $s' =$ $contestcontestcontest...$ 的子串。因此，不存在满足条件的整数 $i$。
注意答案可能无法装入 32 位整数类型，尽管这里不能放入这样的用例。

标签: AtCoder|abc138E

来源

AtCoder|abc138E