Изменения

Разбираемся с двойными дугами (на этом примере из их три). Для этого мы должны выяснить сколько начальных символов таких дуг совпадает. Совпадать может от одного до нескольких символов, или даже все. Проверять их все по очереди нельзя (это даст квадратичное время).

Для примера как это сделать возмём строку <tex>10010010101000</tex>:

Для того чтобы узнать общее начало двойной дуги, мы должны нужно взять одну чётную и одну нечётную на дереве, для которых родителем является конец нашей двойной дуги. Например на рисунке выше двойная дуга <tex>(1)</tex>, конец помечен зелёным - является общим родителем для вершин <tex>3 </tex> и <tex>6</tex>. Чтобы узнать на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на еденицу и найти их родителя, он . Он будет находится на еденицу единицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера). Родителя Родитель вершин <tex>4, </tex> и <tex>7 я пометил </tex> помечен жёлтым, он находится на расстоянии <tex>1 </tex> от корня, следовательно дуга <tex>(1) </tex> должна расслаиваться в двух символах от корня, то есть обе дуги совпадают и их просто надо слить.

* <tex>(1) </tex> расслоение находится на расстоянии два от корня, то есть дуга не расслаивается.* <tex>(2) </tex> конец является родителем вершин <tex>2</tex>, <tex>7</tex>. Родитель <tex>3>/tex>, <tex>8 </tex> после слияния дуги <tex>(1)</tex>, находится на глубине <tex>2 </tex> символа. Значит дуга <tex>(2) </tex> расслаивается на глубине <tex>3 </tex> символа, то есть так же не расслаивается. Дугу <tex>(2) </tex> нужно вычислять после обработки дуги <tex>(1)</tex>, потому что конец дуги <tex>(1) </tex> после обработки может оказаться на разной высоте, в зависимости от того на каком символе она расслоилась.* <tex>(3) </tex> конец является родителем <tex>2</tex>, <tex>9</tex>. Родитель <tex>3</tex>, <tex>10 </tex> находится на расстоянии <tex>3</tex>, а наше расслоение на на расстоянии <tex>4</tex>, то есть сливается первый символ двойной дуги. Дугу <tex>(3) </tex> надо вычислять после дуги <tex>(2)</tex>. Потому что если на дуге <tex>(2) </tex> появится разветвление, то компоненты дуги <tex>(3) </tex> придётся растащить по разным веткам дерева и сравнивать их будет не нужно.* <tex>(4) </tex> конец является родителем <tex>1</tex>, <tex>4</tex>. Расслаивается на втором символе.* <tex>(5) </tex> конец является родителем <tex>0</tex>, <tex>3</tex>. Дугу <tex>(5) </tex> можно обрабатывать только после дуги <tex>(4)</tex>, так как от неё будет зависеть глубина расслояния.