問題一覧 > 通常問題

No.1695 Mirror Mirror

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : eSeF / テスター : stoq ygussany
お気に入りにしたユーザー ProblemId : 6641 / 自分の提出
問題文最終更新日: 2021-09-30 19:31:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 316 (順位表) の他の問題:

Problem Statement

In the following, for a string $U$, $U[l:r]$ denotes the substring of $U$ consisting of the $l$-th through $r$-th characters, and $\text{rev}(U)$ denotes the reversal of $U$. The $+$ operator on strings denotes string concatenation.

You are given a string $S$ of length $N$ and a string $T$ of length $M$, both consisting of lowercase English letters.

You may perform the following two types of operations on $S$ any number of times, in any order.

  • (1) : Choose an integer $i$ satisfying $1\le i\le |S|$, and replace $S$ with $S[1:i] + \text{rev}(S[1:i])$.
  • (2) : Choose an integer $i$ satisfying $1\le i\le |S|$, and replace $S$ with $\text{rev}(S[i:|S|]) + S[i:|S|]$.

Determine whether it is possible to make $S$ equal to $T$ with a finite number of operations. If it is possible, find the minimum total number of operations (1) and (2) required.

Input

$N\ \ M$
$S$
$T$
[Constraints]
  • $1\le N\le 5\times 10^5$
  • $2\le M\le 5\times 10^5$
  • $S,\ T$ are strings consisting of lowercase English letters
  • $|S| = N,\ |T| = M$
  • $S\neq T$
  • $N,\ M$ are integers

Output

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

Sample

Sample 1
Input
5 10
aaabb
bbaabbaabb
Output
2

For example, you can operate as follows.

  • First, apply operation (2) with $i=3$. This gives $S=$ bbaabb.
  • Next, apply operation (1) with $i=5$. This gives $S=$ bbaabbaabb, which is equal to $T$.

It is impossible to make $S=T$ with fewer than $2$ operations. Therefore, the answer is $2$.

Sample 2
Input
4 4
eeic
meip
Output
-1

No matter how you perform the operations, $S=T$ cannot be achieved. In this case, output -1.

Sample 3
Input
24 22
baacbacaababbabaabcbabaa
aabbaabbbbbbbbbbaabbaa
Output
5

Sample 4
Input
25 18
zyxzzyzyzyyzxxyxzyzxzxzyx
xyzzyxzyxxyzxyzzyx
Output
-1

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