AT_abc257_g [ABC257G] Prefix Concatenation

题目描述

给定两个仅由小写英文字母组成的字符串 $S$ 和 $T$。

请你求出一个最小的正整数 $k$，使得可以通过连接 $k$ 个（可以相同也可以不同）$S$ 的前缀，得到字符串 $T$。

也就是说，设 $S_i$ 表示 $S$ 的第 $1$ 个字符到第 $i$ 个字符组成的前缀字符串，那么是否存在 $k$ 个 $1$ 到 $|S|$ 之间的整数 $a_1,a_2,\ldots,a_k$，使得

（这里 $+$ 表示字符串的连接），并求出最小的正整数 $k$。

如果无法通过上述方式得到 $T$，请输出 $-1$。

输入格式

输入以如下格式从标准输入读入：

$S$ $T$

输出格式

输出通过连接 $k$ 个 $S$ 的前缀能够得到 $T$ 的最小正整数 $k$。如果无法得到 $T$，则输出 $-1$。

输入输出样例 #1

输入 #1

aba
ababaab

输出 #1

3

输入输出样例 #2

输入 #2

atcoder
ac

输出 #2

-1

说明/提示

限制条件

• $1 \leq |S| \leq 5 \times 10^5$
• $1 \leq |T| \leq 5 \times 10^5$
• $S,T$ 均为仅由小写英文字母组成的字符串

样例解释 1

$T =$ ababaab 可以表示为 ab + aba + ab，其中 ab 和 aba 都是 $S =$ aba 的前缀。无法用不超过 $2$ 个 $S$ 的前缀连接得到 ababaab，因此输出 $3$。

样例解释 2

无法通过连接 $S$ 的前缀得到 $T$，因此输出 $-1$。

由 ChatGPT 4.1 翻译