ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
33
‒
две замены одного и того же символа (не оптимально, если за-
менили
x
на
y
,
потом
y
на
z
,
то следовало сразу заменить
x
на
z
);
‒
две замены разных символов можно менять местами;
‒
два удаления символа или два добавления можно менять местами;
‒
добавление символа с его последующим удалением (не опти-
мально, так как можно отменить оба действия);
‒
удаление и добавление разных символов можно менять местами;
‒
добавление символа с его последующей заменой (не оптималь-
но, излишняя замена);
‒
добавление символа и замена другого символа меняются ме-
стами;
‒
замена символа с его последующим удалением (не оптимально,
излишняя замена);
‒
удаление символа и замена другого символа меняются местами.
Пусть строка
S
1
заканчивается символом «a», строка
S
2
–
симво-
лом «b», тогда выполняется одно из следующих утверждений.
Утверждение 1.
Символ «a» в некоторый момент времени
удалили из строки
S
1
.
Это удаление будет первой операцией. Затем
превратили первые
i
–1
символов строки
S
1
в символы строки
S
2
(
необходимо
[
]
1,
1
D i
j
− +
операций, т. е. всего
[
]
1,
1
D i
j
− +
опера-
ций).
Утверждение 2.
Символ «b» в определенный момент времени
добавили в строку
S
2
.
Это добавление будет последней операцией.
Превратим символы строки
S
1
в первые
j
–1
символов строки
S
2
,
после
чего добавим символ «b». Для выполнения этих действий потребова-
лось
[
]
, 1 1
D i j
− +
операций.
Утверждение 3.
Пусть утверждения 1 и 2 неверны. Если доба-
вить символы справа от символа «a», то, чтобы символ «b» был по-
следним, следует в некоторый момент времени либо добавить его
(
тогда утверждение 2 верно), либо заменить символ «b» на один из
добавленных символов (что невозможно, поскольку добавление сим-
вола с его последующей заменой не оптимально). Таким образом,
символов справа от символа «a» не добавляли. Сам символ «a» не
удаляли, так как утверждение 1 неверно. Единственный способ изме-
нения последнего символа – его замена. Заменять его 2 или более раз
не оптимально. В результате возможны два варианта:
‒
если символы «a» и «b» совпадают, то последний символ не
меняют. Поскольку его также не удаляют и не добавляют ничего
справа от него, то он не влияет на действия. Соответственно, выпол-
няют
[
]
1, 1
D i
j
− −
операций, т. е.
[ ] [ ]
1
2
(
,
) 0
m S i S j
=
;
‒
если символы «a» и «b» не совпадают, то последний символ
меняют 1 раз. Выполним эту замену первой. Далее, аналогично