Prefix Concatenation

题目描述

给定两个由小写英文字母组成的字符串 $S$ 和 $T$。 找出最小的正整数 $k$，使得你可以选择（不必互不相同的）$k$ 个 $S$ 的前缀，使得它们的串联与 $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$ 表示 $S$ 的从第 $1$ 个字符到第 $i$ 个字符的子串，$+$ 表示字符串的串联。 如果不可能使其与 $T$ 一致，则输出 $-1$。

输入格式

输入由标准输入按以下格式给出： $S$ $T$

输出格式

输出最小的正整数 $k$，使得你可以选择 $k$ 个 $S$ 的前缀，使得它们的串联与 $T$ 相同。 如果不可能使其与 $T$ 一致，输出 $-1$。

aba
ababaab

3

atcoder
ac

-1

提示

$1 \leq |S| \leq 5\times 10^5$ $1 \leq |T| \leq 5\times 10^5$ $S$ 和 $T$ 是由小写英文字母组成的字符串。$T=$ $ababaab$ 可以写成 $ab$ + $aba$ + $ab$，其中 $ab$ 和 $aba$ 是 $S=$ $aba$ 的前缀。
由于无法用两个或更少的 $aba$ 的前缀表示 $ababaab$，输出 $3$.
由于无法将 $T$ 表示为若干 $S$ 的前缀的串联，输出 $-1$.

标签: AtCoder|abc257G

来源

AtCoder|abc257G