Решение задачи 11.
Если последовательности B и C совпадают, то вычеркнутых букв определить нельзя.
Если B и C различаются ровно в одной позиции (т.е. в A были вычеркнуты соседние буквы), то определить вычеркнутые буквы можно, а последовательность A - нет (пример: A='ABCDB', B='ACDB', C='ABDB').
Чуть-чуть упростим задачу. Уберем из начала и конца последовательностей B и C все совпадающие элементы. Получим последовательности B' и C'. Пример B='albce', C='alcde', B'='bc', C'='cd', т.к. первые два и последний символ у B и C совпадают. Если мы сможем восстановить слово, из которого получается B' и C', то мы сможем восстановить и A.
Пусть B'=b1b2b3 ... bk
C'=c1c2c3 ... ck.
Если b1=c2=b3=c4= ... и (*)
C1=b2=c3=b4= ...,
то определить последовательность A нельзя, выброшенные буквы
- это b1 и c1.
Пример: B='abab', C='baba'. В качестве A можно взять как
'babab', так и 'ababa').
Если же (*) не выполняется, то можно найти и A, и вычеркнутые
буквы. Мы находим такие элементы в B' и C', что c(i)=b(i+1) и b(i)<>c(i+1) (или c(i)<>b(i+1), а b(i)=c(i+1)), и получаем начальную строчку A=b(1) ... b(i)b(i+1)c(i+1)b(i+2)
... b(k) (или A=c(1) ... c(i)c(i+1)b(i+1)c(i+2) ... c(k)).
Пример: B'='bc'
C'='cd'
Слово из которого получается и B' и C' - 'bcd'.
|
