← 返回题目列表

AtCoder · abc138_e

E. 杂质串

中文机器翻译题面 查看原题

分数: 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位整数类型,尽管我们不能在这里放置这种情况。