No.1695 Mirror Mirror
タグ : / 解いたユーザー数 16
作問者 :
eSeF
/ テスター :
stoq
ygussany
問題文
以下では、文字列 $U$ に対して $U[l:r]$ で $U$ の $l$ 文字目から $r$ 文字目を取り出した部分文字列を、また $\text{rev}(U)$ で $U$ を反転した文字列を表すことにします。 また、文字列に対する $+$ 演算子は文字列の連結を表すものとします。
英小文字からなる長さ $N$ の文字列 $S$ と長さ $M$ の文字列 $T$ が与えられます。
あなたは $S$ に対して、以下の２種類の操作を任意の回数、任意の順番で行う事ができます。
- (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もしくは右上の雲マークをクリックしてアカウントを作成してください。