1215 - 形成字符串的最短路径

对于任何字符串,我们可以通过删除其中一些字符(也可能不删除)来构造该字符串的 子序列 。(例如,“ace” 是 “abcde” 的子序列,而 “aec” 不是)。

给定源字符串 source 和目标字符串 target,返回 源字符串 source 中能通过串联形成目标字符串 target 的 子序列 的最小数量 。如果无法通过串联源字符串中的子序列来构造目标字符串,则返回 -1。

输入

输入2个字符串,source和target

输出

输出 源字符串 source 中能通过串联形成目标字符串 target 的 子序列 的最小数量 。如果无法通过串联源字符串中的子序列来构造目标字符串,则输出 -1。

样例

输入

abc
abcbc

输出

2

输入

abc
acdbc

输出

-1

输入

xyz
xzyxz

输出

3

提示

1 \leq source.length, target.length \leq 1000 source 和 target 仅包含英文小写字母。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题