C - Insert and Erase A 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

英大文字からなる文字列 S,T が与えられます。

あなたは以下の 2 種類の操作を好きな順序で好きな回数（0 回でも良い）行うことができます。

  • S の好きな位置（先頭および末尾を含む）に文字 A を 1 つ挿入する。
  • S に含まれる文字 A を 1 つ選んで削除する。なお、残った文字は元の順序を保ったまま連結される。

S を T に一致させることが可能かどうか判定し、可能な場合は必要な操作回数の合計の最小値を求めてください。

制約

  • S,T は英大文字からなる長さ 1 以上 3\times 10^5 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

S を T に一致させることが可能ならば必要な操作回数の合計の最小値を、不可能ならば -1 を出力せよ。

入力例 1

ABC
BACA

出力例 1

3

以下のように、合計 3 回の操作で S を T に一致させることが可能です。

  • S の 2 文字目と 3 文字目の間に A を 1 つ挿入する。S= ABAC となる。
  • S の 1 文字目にある A を削除する。S= BAC となる。
  • S の末尾に A を 1 つ挿入する。S= BACA となる。

合計 2 回以下の操作で S を T に一致させることはできないため、答えは 3 です。

入力例 2

ABC
ARC

出力例 2

-1

どのように操作を行っても、S を T に一致させることはできません。

入力例 3

ABC
ABC

出力例 3

0

1 回も操作を行う必要がありません。

入力例 4

AAAWAZAAAABAAAU
AWAAZABAAAAAUA

出力例 4

9

Score : 300 points

Problem Statement

You are given strings S and T consisting of uppercase English letters.

You may perform the following two types of operations any number of times (possibly zero) in any order:

  • Insert one character A at any position in S (possibly the beginning or the end).
  • Choose one character A in S and delete it. The remaining characters are concatenated in their original order.

Determine whether it is possible to make S equal to T, and if so, find the minimum total number of operations required.

Constraints

  • S and T are strings of uppercase English letters with length between 1 and 3\times 10^5, inclusive.

Input

The input is given from Standard Input in the following format:

S
T

Output

If it is possible to make S equal to T, output the minimum total number of operations required; otherwise, output -1.

Sample Input 1

ABC
BACA

Sample Output 1

3

It is possible to make S equal to T in three operations in total, as follows:

  • Insert one A between the second and third characters of S. Now, S= ABAC.
  • Delete the first character of S, which is A. Now, S= BAC.
  • Insert one A at the end of S. Now, S= BACA.

It is impossible to make S equal to T in two or fewer operations, so the answer is 3.

Sample Input 2

ABC
ARC

Sample Output 2

-1

No matter how operations are performed, it is impossible to make S equal to T.

Sample Input 3

ABC
ABC

Sample Output 3

0

No operations need to be performed.

Sample Input 4

AAAWAZAAAABAAAU
AWAAZABAAAAAUA

Sample Output 4

9