AT_abc138_e [ABC138E] Strings of Impurity

题目描述

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

样例 1

输入

contest
son

输出

10

样例 2

输入

contest
programming

输出

-1

样例 3

输入

contest
sentence

输出

33

说明/提示

注释

• 字符串 $a$ 的子序列是指从 $a$ 中删除 $0$ 个或多个字符后，按原有顺序连接剩下的字符所得到的字符串。例如，contest 的子序列包括 net、c、contest 等。

约束条件

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

样例解释 1

$t = \text{son}$ 是字符串 contestcon（即 $s' = \text{contestcontestcontest...}$ 的前 $10$ 个字符）的一个子序列，因此 $i = 10$ 满足条件。而 $t$ 不是字符串 contestco（$s'$ 的前 $9$ 个字符）的子序列，因此 $i = 9$ 不满足条件。同理，$8$ 及以下的任意整数也不满足条件。因此，满足条件的最小整数 $i$ 为 $10$。

样例解释 2

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

样例解释 3

虽然这里无法给出这样的样例，但请注意，答案可能不会落在 $32$ 位整数范围内。

由 ChatGPT 4.1 翻译