171
правка
Изменения
Нет описания правки
<tex>a_i = \#_q d</tex>, <tex>b_i = \#_p c</tex>.
Такие последовательности позволяют сформировать строки <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_n \$</tex> (из <tex>a</tex>) и <tex>\$ snap_1 \$ snap_2 \$ \ldots \$ snap_{n-1} \$</tex> (из <tex>b</tex>)и только их, но решения МПСП быть не может, так как все члены последовательностей, кроме первого, имеют равную длину, и строка, составленная из элементов <tex>a</tex>, всегда оказывается длиннее.
Задача — получить равные строки, если состояние <tex>\#_{yes}</tex> достижимо. Для этого добавим в уже имеющиеся последовательности следующие элементы:
а также
<tex>a_i = \$ \$</tex>, <tex>b_i = <tex> \#_{yes} \$ \$</tex>.
С помощью новых элементов можно привести обе строки к виду
{| border="1"
|Номер элемента
|width="4560"|1 |width="4560"|2 |width="4560"|3 |width="4560"|4 |width="4560"|5 |width="4560"|6 |width="4560"|7 |width="4560"|8 |width="4560"|9 |width="4560"|10 |width="4560"|11
|-
|Последовательность a
|<tex>\$ \#_{start} a ab \$</tex>
|<tex>a</tex>
|<tex>b</tex>
|<tex>\#_{yes}</tex>
|<tex>\#_{yes}</tex>
|<tex>\$ \$</tex>
|-
|Последовательность b
|}
Решение МПСП будет иметь следующий вид:
{| border="1"
|Шаг
|Индекс элемента
|Первая строка
|Вторая строка
|-
|1
|1
|<tex>\$ \#_{start} ab \$</tex>
|<tex>\$</tex>
|-
|2
|5
|<tex>\$ \#_{start} ab \$ b \#_{start}</tex>
|<tex>\$ \#_{start} a</tex>
|-
|3
|3
|<tex>\$ \#_{start} ab \$ b \#_{start} b</tex>
|<tex>\$ \#_{start} ab</tex>
|-
|4
|4
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$</tex>
|<tex>\$ \#_{start} ab \$</tex>
|-
|5
|3
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b</tex>
|<tex>\$ \#_{start} ab \$ b</tex>
|-
|6
|6
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b</tex>
|<tex>\$ \#_{start} ab \$ b \#_{start} b</tex>
|-
|7
|4
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$</tex>
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$</tex>
|-
|8
|8
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes}</tex>
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes}</tex>
|-
|9
|3
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b</tex>
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b</tex>
|-
|10
|4
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$</tex>
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$</tex>
|-
|11
|10
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes}</tex>
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b</tex>
|-
|12
|4
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$</tex>
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$</tex>
|-
|13
|11
|<tex>\$ \#_{start} ab \$ b \#_{start} b\$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$</tex>
|<tex>\$ \#_{start} ab \$ b \#_{start} b \$ b \#_{yes} b \$ \#_{yes} b \$ \#_{yes} \$ \$</tex>
|}
