← 返回题目列表

AtCoder · abc447_c

F. 插入和删除 A

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你字符串 S 和 T 由大写英文字母组成。

您可以按任意顺序执行任意次数(可能为零)以下两种类型的操作:

  • 插入一个字符 A 在任何位置 S (可能是开头或结尾)。
  • 选择一个角色 A in 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