Изменения

Пусть даны последовательности <tex>a, b</tex> из условия МПСП. Обозначим как <tex>left(w, c)</tex> и <tex>right(w, c)</tex> строки, состоящие из символов <tex>w</tex>, разделённых <tex>c</tex>: <tex>left(w, c) = c w_1 c w_2 \ldots c w_k</tex>, <tex>right(w, c) = w_1 c w_2 c \dots w_k c</tex>. Построим две новые последовательности <tex>a', b'</tex>:* <tex>a'_1 = \$ right(a_1 , \$)</tex>, <tex>b'_1 = left(b_1, \$ b_1)</tex>;* <tex>\forall i = 1 .. n</tex>: <tex>a'_{i+1} = right(a_i , \$)</tex>, <tex>b'_{i+1} = left(b_i, \$ b_i)</tex>;

Пусть  <tex>w_a = a_1 a_{i_2} \ldots a_{i_k} </tex>, <tex>w_b = b_1 b_{i_2} \ldots b_{i_k}</tex>, <tex>w_a = w_b</tex>. Тогда Рассмотрим <tex>w'_a = a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = \$ right(a_1 , \$ ) right(a_{i_2} , \$ ) \ldots \$ right(a_{i_k} , \$ ) \#</tex>,  <tex>w'_b = b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2} = \$ left(b_1 , \$ ) left(b_{i_2} , \$ ) \ldots \$ left(b_{i_k} , \$) \$ \#</tex>. На чётных позициях в <tex>w'_a</tex> и <tex>w'_b</tex> стоят равные символы из <tex>w_a</tex> и <tex>w_b</tex>, следовательноа также <tex>\#</tex> (в конце); на нечётных — <tex>\$</tex>. Следовательно,  <tex>a'_1 a'_{i_2+1} \ldots a'_{i_k+1} a'_{n+2} = b'_1 b'_{i_2+1} \ldots b'_{i_k+1} b'_{n+2}</tex>.

Пусть  <tex>a'_1 a'_{i_2} \ldots a'_{i_k} = b'_1 b'_{i_2} \ldots b'_{i_k}</tex>.  Если <tex>i_f</tex> — наименьший индекс, равный <tex>n+2</tex>, то <tex>a'_1 a'_{i_2} \ldots a'_{i_f}</tex>, <tex>b'_1 b'_{i_2} \ldots b'_{i_f}</tex> — префиксы исходных конкатенаций до первого символа <tex>\#</tex>, следовательно, равны между собой. <tex>i_1, \ldots, i_f</tex> — также решение ПСП, причём <tex>i_1 = 1</tex>, <tex>i_f = n + 2</tex>. Остальные индексы не превосходят <tex>n+1</tex>, но и не равны <tex>1</tex>, иначе в левой части равенства образуется подстрока из двух <tex>\$</tex> подряд, а в правой её не будетможет быть. Учитывая эти ограничения, перепишем получившееся равенство:  <tex>\$ right(a_1 , \$ ) right(a_{i_2-1} , \$ ) \ldots \$ right(a_{i_{f-1}-1} , \$ ) \# </tex> <tex>= \$ </tex> <tex>left(b_1 , \$ ) left(b_{i_2-1} , \$ ) \ldots \$ left(b_{i_{f-1}-1} , \$) \$ \#</tex>. Оставив из этих двух строк символы, а значитстоящие на чётных позициях, и удалив с конца <tex>\#</tex>, получим <tex>a_1 a_{i_2-1} \ldots a_{i_{f-1}-1} = b_1 b_{i_2-1} \ldots b_{i_{f-1}-1}</tex>.