4988：子序列匹配
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 子序列匹配
## 题目描述
给定两个**仅由小写英文字母**组成的字符串 $S$ 和 $T$ 。
考虑将字符串 $S$ **无限次拼接**而成的**无限长字符串** $S' = SSS\cdots$ （即 $S$ **重复**无限多次）。例如，若 $S = \text{abc}$ ，则 $S' = \text{abcabcabc}\cdots$ 。
定义：字符串 $A$ 的子序列是指从 $A$ 中删除**零个或任意多个字符**后，将剩余字符按**原有相对顺序**连接而成的字符串。如：字符串 ABCDE 的子序列可以有：ABCDE、ABDE、ACE、CDE、E $\cdots$ 。但根据定义，字符串 ABCDE 的子序列**一定不可能**有 ABEDC、CAE、EDCBA。
现在要求：判断是否存在正整数 $i$ ，使得 $T$ 是 $S'$ 的前 $i$ 个字符构成的字符串的一个子序列。
如果存在这样的 $i$ ，请输出满足条件的**最小** $i$ ；如果不存在任何满足条件的 $i$ ，请输出 $-1$ 。
## 输入格式
第一行输入仅由小写字母组成的字符串 $S$ 。
第二行输入仅由小写字母组成的字符串 $T$ 。
## 输出格式
输出一个整数，表示满足条件的最小 $i$ 。如果不存在，请输出 $-1$ 。
## 样例
### 样例输入 1
```text
contest
son
```
### 样例输出 1
```text
10
```
### 样例输入 2
```text
contest
programming
```
### 样例输出 2
```text
-1
```
### 样例输入 3
```text
contest
sentence
```
### 样例输出 3
```text
33
```
## 说明/提示
样例说明 1
对于 $S=\text{contest}$ 、 $T=\text{son}$ ：
- 当 $i=10$ 时， $s'$ 的前 10 个字符为 contestcon。
- 可以从中依次选取位置 3 的 s、位置 8 的 o、位置 10 的 n，构成 son。
- 当 $i=9$ 时，前缀为 contestco，无法找到足够的 n 来完成匹配。
- 因此 $10$ 是满足条件的最小值。
样例说明 2
对于 $T=\text{programming}$ ，无论将 $S=\text{contest}$ 重复多少次，其前缀中都不存在按顺序出现 p、r、o、g、r、a、m、m、i、n、g 所需的全部字母（缺少 p、g 等关键字母），故不存在满足条件的 $i$ ，输出 $-1$ 。
数据范围
| 测试点编号 | $|S|$ | $|T|$ |
|---|---|---|
| $1 \sim 2$ | $|S|=1$ | $|T|=1$ |
| $3 \sim 4$ | $|S|=2$ | $|T|=1$ |
| $5 \sim 6$ | $|S|=1$ | $|T|=2$ |
| $7 \sim 25$ | $1 \le |S| \le 10^5$ | $1 \le |T| \le 10^5$ |
对于 $100\%$ 的数据，满足 $1 \le |S| \le 10^5$ ， $1 \le |T| \le 10^5$ ， $S$ 和 $T$ 均仅由小写英文字母组成。（ $|S|$ 表示字符串 $S$ 的长度）
---
**题目来源：** 26年3月-B组（才俊）