問題一覧 > 通常問題

No.1695 Mirror Mirror

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : eSeFeSeF / テスター : stoqstoq 👑 ygussanyygussany
8 ProblemId : 6641 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-30 19:31:47

問題文

以下では、文字列 $U$ に対して $U[l:r]$ で $U$ の $l$ 文字目から $r$ 文字目を取り出した部分文字列を、また $\text{rev}(U)$ で $U$ を反転した文字列を表すことにします。 また、文字列に対する $+$ 演算子は文字列の連結を表すものとします。

英小文字からなる長さ $N$ の文字列 $S$ と長さ $M$ の文字列 $T$ が与えられます。

あなたは $S$ に対して、以下の2種類の操作を任意の回数、任意の順番で行う事ができます。

  • (1) : $1\le i\le |S|$ を満たす整数 $i$ を選び、$S$ を $S[1:i] + \text{rev}(S[1:i])$ に置き換える。
  • (2) : $1\le i\le |S|$ を満たす整数 $i$ を選び、$S$ を $\text{rev}(S[i:|S|]) + S[i:|S|]$ に置き換える。

有限回の操作で $S$ を $T$ に一致させることが可能か判定してください。 可能な場合、それに要する (1) と (2) の操作回数の和の最小値を求めてください。

入力

$N\ \ M$
$S$
$T$
【制約】
  • $1\le N\le 5\times 10^5$
  • $2\le M\le 5\times 10^5$
  • $S,\ T$ は英小文字からなる文字列
  • $|S| = N,\ |T| = M$
  • $S\neq T$
  • $N,\ M$ は整数

出力

$S$ を $T$ に一致させる事が可能ならば、それに要する操作回数の最小値を出力せよ。 不可能ならば、-1 を出力せよ。

サンプル

サンプル1
入力
5 10
aaabb
bbaabbaabb
出力
2

例えば、以下のように操作すると良いです。

  • まず、操作 (2) で $i=3$ とします。$S=$ bbaabb となります。
  • 次に、操作 (1) で $i=5$ とします。$S=$ bbaabbaabb となり、$T$ に一致します。

$2$ 回未満の操作で $S=T$ とすることはできません。よって、答えは $2$ です。

サンプル2
入力
4 4
eeic
meip
出力
-1

操作をどのように行っても、$S=T$ にはなりません。この場合は -1 を出力してください。

サンプル3
入力
24 22
baacbacaababbabaabcbabaa
aabbaabbbbbbbbbbaabbaa
出力
5

サンプル4
入力
25 18
zyxzzyzyzyyzxxyxzyzxzxzyx
xyzzyxzyxxyzxyzzyx
出力
-1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。