分数: 500 点
问题陈述
给定两个字符串 s 和 t 由小写英文字母组成。判断是否存在整数 i 满足以下条件,并找到这样的最小值 i (如果存在)。
- 让 s' 是以下的串联 10^{100} 副本 s. t 是字符串的子序列 {s'}_1{s'}_2\ldots{s'}_i (第一个 i 中的字符 s').
注释
- 字符串的子序列 a 是删除零个或多个字符得到的字符串 a 并连接其余字符而不改变相对顺序。例如,以下的子序列
contest包括net,c,和contest.
约束
- 1 \leq |s| \leq 10^5
- 1 \leq |t| \leq 10^5
- s 和 t 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
s t
输出
如果存在整数 i 满足以下条件,打印最小这样的 i;否则,打印 -1.
示例输入 1
contest son
示例输出 1
10
t = son 是字符串的子序列 contestcon (第一个 10 中的字符 s' = contestcontestcontest...),所以 i = 10 满足条件。
另一方面, t 不是字符串的子序列 contestco (第一个 9 中的字符 s'),所以 i = 9 不满足条件。
类似地,任何小于 9 也不满足条件。因此,最小整数 i 满足条件是 10.
示例输入 2
contest programming
示例输出 2
-1
t = programming 不是以下的子串 s' = contestcontestcontest...。因此,不存在整数 i 满足条件。
示例输入 3
contest sentence
示例输出 3
33
请注意,答案可能不适合 32位整数类型,尽管我们不能在这里放置这种情况。