No.1695 Mirror Mirror
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
eSeF
stoq