Score : $600$ points

问题描述

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

找出最小的正整数 $k$，使得你可以选择（不一定互不相同）$S$ 的 $k$ 个前缀，使得它们连接起来与 $T$ 相吻合。

换句话说，找到最小的正整数 $k$，使得存在一个包含 $1$ 到 $|S|$ 之间的整数的 $k$ 元组 $(a_1, a_2, \ldots, a_k)$，满足以下条件：

$$T = S_{a_1} + S_{a_2} + \cdots + S_{a_k}$$

其中，$S_i$ 表示从第 $1$ 个字符到第 $i$ 个字符的 $S$ 的子串，而 $+$ 表示字符串的连接操作。

如果无法使它与 $T$ 相吻合，则输出 $-1$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given two strings $S$ and $T$ consisting of lowercase English letters.

Find the minimum positive integer $k$ such that you can choose (not necessarily distinct) $k$ prefixes of $S$ so that their concatenation coincides with $T$.

In other words, find the minimum positive integer $k$ such that there exists a $k$-tuple $(a_1,a_2,\ldots, a_k)$ of integers between $1$ and $|S|$ such that
$T=S_{a_1}+S_{a_2}+\cdots +S_{a_k}$, where $S_i$ denotes the substring of $S$ from the $1$-st through the $i$-th characters and $+$ denotes the concatenation of strings.

If it is impossible to make it coincide with $T$, print $-1$ instead.

Constraints

• $1 \leq |S| \leq 5\times 10^5$
• $1 \leq |T| \leq 5\times 10^5$
• $S$ and $T$ are strings consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$S$

$T$

Output

Print the minimum positive integer $k$ such that you can choose $k$ prefixes of $S$ so that their concatenation coincides with $T$. It is impossible to make it coincide with $T$, print $-1$ instead.

Sample Input 1

aba
ababaab

Sample Output 1

3

$T=$ ababaab can be written as ab + aba + ab, of which ab and aba are prefixes of $S=$ aba.
Since it is unable to express ababaab with two or less prefixes of aba, print $3$.

Sample Input 2

atcoder
ac

Sample Output 2

-1

Since it is impossible to express $T$ as a concatenation of prefixes of $S$, print $-1$.

update @ 2024/3/10 10:56:14