Вдохновением для задачи послужила история компании Pied Piper. После анонса технологии Nucleus со стороны конкурирующей компании Hooli Ричард при содействии друзей изобрёл принципиально новый подход к сжатию: «из середины наружу».
Вам даны две строки \(s\) и \(t\) одинаковой длины \(n\). Пронумеруем их символы то \(1\) до \(n\) слева направо (т.е. от начала к концу)
За один ход вы можете сделать следующую последовательность действий:
- выбрать произвольный индекс \(i\) (\(1 \le i \le n\)),
- передвинуть \(i\)-й символ строки \(s\) с текущей позиции в начало строки или передвинуть \(i\)-й символ строки \(s\) с текущей позиции в конец строки.
Заметим, что длина строки \(s\) в результате хода не поменяется. Вы можете применить ход только к строке \(s\).
Например, если \(s=\)«test», то за один ход можно получить:
- если \(i=1\) и вы перемещаете символ в начало, то результат будет равен «test» (строка не изменяется),
- если \(i=2\) и вы перемещаете символ в начало, то результат будет равен «etst»,
- если \(i=3\) и вы перемещаете символ в начало, то результат будет равен «stet»,
- если \(i=4\) и вы перемещаете символ в начало, то результат будет равен «ttes»,
- если \(i=1\) и вы перемещаете символ в конец, то результат будет равен «estt»,
- если \(i=2\) и вы перемещаете символ в конец, то результат будет равен «tste»,
- если \(i=3\) и вы перемещаете символ в конец, то результат будет равен «tets»,
- если \(i=4\) и вы перемещаете символ в конец, то результат будет равен «test» (строка не изменяется).
Вы хотите преобразовать строку \(s\) в строку \(t\). Какое минимальное количество ходов для этого потребуется? Если преобразовать \(s\) в \(t\) невозможно, выведите -1.
Выходные данные
Для каждого набора входных данных выведите минимальное количество ходов, которое нужно чтобы превратить \(s\) в \(t\) или -1, если это сделать невозможно.
Примечание
В первом примере, ходы в одном из оптимальных ответов выглядят следующим образом:
- в первом наборе: \(s=\)«iredppipe», \(t=\)«piedpiper»: «iredppipe» \(\rightarrow\) «iedppiper» \(\rightarrow\) «piedpiper»;
- во втором наборе: \(s=\)«estt», \(t=\)«test»: «estt» \(\rightarrow\) «test»;
- в третьем наборе: \(s=\)«tste», \(t=\)«test»: «tste» \(\rightarrow\) «etst» \(\rightarrow\) «test».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
9
iredppipe
piedpiper
4
estt
test
4
tste
test
|
2
1
2
|
|
2
|
4
1
a
z
5
adhas
dasha
5
aashd
dasha
5
aahsd
dasha
|
-1
2
2
3
|