分数: 300 点
问题陈述
给你字符串 S 和 T 由大写英文字母组成。
您可以按任意顺序执行任意次数(可能为零)以下两种类型的操作:
- 插入一个字符
A在任何位置 S (可能是开头或结尾)。 - 选择一个角色
Ain S 并将其删除。其余字符按其原始顺序连接。
判断是否可以使 S 等于 T,如果是,则找到所需的最小操作总数。
约束
- S 和 T 是大写英文字母的字符串,长度介于 1 和 3\times 10^5,包括在内。
输入
输入由标准输入按以下格式给出:
S T
输出
如果可以的话 S 等于 T,输出所需的最小操作总数;否则,输出 -1.
示例输入 1
ABC BACA
示例输出 1
3
可以使 S 等于 T 一共进行了3次操作,如下:
- 插入一个
A第二个和第三个字符之间 S。现在, S=ABAC. - 删除第一个字符 S,即
A。现在, S=BAC. - 插入一个
A结束时 S。现在, S=BACA.
不可能使 S 等于 T 两次或更少的操作,所以答案是 3.
示例输入 2
ABC ARC
示例输出 2
-1
无论怎样操作,都不可能使 S 等于 T.
示例输入 3
ABC ABC
示例输出 3
0
无需执行任何操作。
示例输入 4
AAAWAZAAAABAAAU AWAAZABAAAAAUA
示例输出 4
9