Сжатое суффиксное дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Поиск строки максимальной длины, ветвящейся влево и вправо v 1.0)
(Поиск строки максимальной длины, ветвящейся влево и вправо 1.1)
Строка 178: Строка 178:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>, если существуют символы <tex>c</tex> и <tex>d</tex>, такие что <tex>c</tex> <tex>\ne</tex> <tex>d</tex> : <tex>sc</tex> и <tex>sd</tex> - подстроки <tex>t</tex>. Аналогично, ветвящаяся влево, если <tex>cs</tex> и <tex>ds</tex> - подстроки <tex>t</tex>.
+
'''Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>''' (англ. ''right merging string''), если существуют символы <tex>c</tex> и <tex>d</tex>, такие что <tex>c</tex> <tex>\ne</tex> <tex>d</tex> : <tex>sc</tex> и <tex>sd</tex> {{---}} подстроки <tex>t</tex>. Аналогично, '''ветвящаяся влево''' (англ. ''left merging''), если <tex>cs</tex> и <tex>ds</tex> {{---}} подстроки <tex>t</tex>.
 
}}
 
}}
[[Файл:RightMergingSS.png|thumb|right|Суффиксное дерево для строки <tex>aabcabd</tex>]]
+
[[Файл:RightMergingSS.png|center|Суффиксное дерево для строки <tex>aabcabd</tex>]]
Первая часть алгоритма: построим Суффиксное дерево при помощи [[Алгоритм Укконена|Алгоритма Укконена]]. При создании ответвления будем увеличивать счётчик вершины, от которой идёт новый лист, на 1, если его пометка <tex>\ne</tex> <tex>\$</tex>. Таким образом, если у вершины счётчик <tex>></tex> 1, то подстрока, которую мы восстановим, идя вверх по дереву до корня, будет ветвящейся вправо (в примере для строки <tex>aabcabd</tex> это <tex>b</tex>, <tex>a</tex> и <tex>ab</tex>). Далее введём термины ''левый символ'' и ''вершина различная влево'', что бы найти строки, ветвящиеся влево.
+
Построим cуффиксное дерево при помощи [[Алгоритм Укконена|Алгоритма Укконена]]. В полученном дереве не листовой вершине <tex>v</tex> будет соответствовать подстрока <tex>s</tex>, которая ветвится вправо, при условии, что количество "хороших" детей вершины <tex>v > 2</tex> ("хорошие" дети - листы, метка которых <tex>\ne\$</tex>). В примере для строки <tex>aabcabd</tex> это <tex>b</tex>, <tex>a</tex> и <tex>ab</tex>. Далее введём термины ''левый символ'' и ''вершина различная влево'', что бы найти строки, ветвящиеся влево.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Левый символ''' для позиции <tex>i</tex> строки <tex>S</tex> - это символ <tex>S(i-1)</tex>.
+
'''Левый символ''' для позиции <tex>i</tex> строки <tex>S</tex> {{---}} это символ <tex>S(i-1)</tex>.
'''Левым символом''' листа <tex>L</tex> называется левый символ начала суффикса, представляемого этим листом.
+
'''Левым символом''' листа <tex>L</tex> называется ''левый символ'' начала суффикса, ведущего в этот лист.
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 195: Строка 195:
 
о строке, ветвящейся вправо и влево
 
о строке, ветвящейся вправо и влево
 
|statement=
 
|statement=
Строка <tex>a</tex>, соответствующая пути к вершине <tex>v</tex>, является ветвящейся вправо и влево тогда и только тогда, когда вершина <tex>v</tex> ''различна влево'' и счётчик вершины <tex>></tex> 1.
+
Строка <tex>a</tex>, соответствующая пути к вершине <tex>v</tex>, является ветвящейся вправо и влево тогда и только тогда, когда вершина <tex>v</tex> ''различна влево'' и счётчик вершины <tex>> 1</tex>.
 
|proof=
 
|proof=
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
*Предположим, что <tex>v</tex> различна влево. Значит, что существуют подстроки <tex>cs</tex> и <tex>ds</tex>.
+
 
*Пусть за первой подстрокой следует символ <tex>p</tex>. Если за второй подстрокой следует символ, <tex>\ne p</tex>, то <tex>s</tex> - строка, ветвящаяся вправо и влево.
+
Предположим, что <tex>v</tex> различна влево. Значит, что существуют подстроки <tex>cs</tex> и <tex>ds</tex>. Пусть за первой подстрокой следует символ <tex>p</tex>. Если за второй подстрокой следует символ, <tex>\ne p</tex>, то <tex>s</tex> - строка, ветвящаяся вправо и влево. Так как у <tex>v</tex> есть два различных ребёнка, которые начинаются с различных символов <tex>p,q \ne \$</tex>, строка является ветвящейся вправо.
*Так как у <tex>v</tex> есть два различных ребёнка, которые начинаются с различных символов <tex>p,q \ne \$</tex>, строка является ветвящейся вправо.
 
  
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
*Пусть строка <tex>s</tex> является ветвящейся вправо и влево.
+
 
*Тогда существуют подстроки <tex>csa</tex> и <tex>dsb</tex>.
+
Пусть строка <tex>s</tex> является ветвящейся вправо и влево. Тогда существуют подстроки <tex>csa</tex> и <tex>dsb</tex>. В суффиксном дереве существует вершина <tex>v</tex> соответствующая строке <tex>s</tex> (так как есть как минимум два суффикса, начинающиеся со строки <tex>s</tex>). У вершины <tex>v</tex>, есть как минимум два ребёнка, которые начинаются с символов <tex>a</tex> и <tex>b</tex> <tex>\Rightarrow</tex> счётчик вершины <tex>> 2</tex>. Так же у вершины <tex>v</tex>, есть как минимум два ребёнка, у которых ''левый символ'' <tex>c</tex> и <tex>d</tex>, значит вершина <tex>v</tex> ''различна влево'' по определению.
*В суффиксном дереве существует вершина <tex>v</tex> соответствующая строке <tex>s</tex> (так как есть как минимум два суффикса, начинающиеся со строки <tex>s</tex>).
 
*У вершины <tex>v</tex>, есть как минимум два ребёнка, которые начинаются с символов <tex>a</tex> и <tex>b</tex> <tex>\Rightarrow</tex> счётчик вершины <tex>></tex> 2.
 
*Так же у вершины <tex>v</tex>, есть как минимум два ребёнка, у которых ''левый символ'' <tex>c</tex> и <tex>d</tex>, значит вершина <tex>v</tex> ''различна влево'' по определению.
 
 
}}
 
}}
  
Будем хранить в вершинах суффиксного дерева следующую информацию: левый символ или флаг, означающий, что вершина различна влево.
+
Что бы найти строки, ветвящиеся влево, нужно проверить все вершины суффиксного дерева на различность влево. Если какая-то вершина <tex>v</tex> будет различна влево и удволетворять свойству ветвимости право, то строка, соответствующая вершине <tex>v</tex> будет ветвится вправо и влево по теореме.
Вторая часть алгоритма начинает с листов суффиксного дерева, записывая для них левый символ. Затем мы обрабатываем вершины снизу вверх. При обработке вершины <tex>v</tex> проверяются её дети, если хотя бы один из них различен влево, то записываем, что вершина <tex>v</tex> различна влево.  
+
 
Если никто из детей не различен влево, то проверяем их символы, привязанные к вершинам детей.
+
Что бы найти вершины различные влево будем хранить левый символ для каждой вершины, пусть он будет <tex>\$</tex>, если вершина различна влево. Что бы промаркировать всё дерево, нужно записать левые символы для листов, а затем подниматься вверх по дереву. Для каждой вершины <tex>v</tex> будем запускать проверку:
Если все символы равны <tex>x</tex>, то запишем в <tex>v x</tex>, иначе запишем в <tex>v</tex>, что она различна влево.
+
*Если среди левых символов детей <tex>v</tex> есть хотя бы один <tex>\$</tex>, то запишем в <tex>v</tex> <tex>\$</tex> и закончим проверку.
Так как время проверки детей <tex>v</tex> пропорционально числу детей, время работы всего алгоритма - <tex>O(n)</tex>.
+
*Если среди левых символов детей <tex>v</tex> нет ни одного <tex>\$</tex>, то проверим на совпадение левые символы детей:
 +
**Если все левые символ детей <tex>v</tex> одинаковы и эквивалентны <tex>x</tex>, то запишем в <tex>v</tex> <tex>x</tex>.
 +
**Если не все левые символы детей <tex>v</tex>, то запишем в <tex>v</tex> <tex>\$</tex> {{---}} вершина различна влево.
 +
 
 +
Так как время проверки <tex>v</tex> пропорционально числу детей, время работы всего алгоритма {{---}} <tex>O(n)</tex>.
  
 
Далее соберём все строки удовлетворяющие условию теоремы и найдём среди них максимальную (так же этот алгоритм можно использовать для нахождения количества строк, ветвящихся влево и вправо).   
 
Далее соберём все строки удовлетворяющие условию теоремы и найдём среди них максимальную (так же этот алгоритм можно использовать для нахождения количества строк, ветвящихся влево и вправо).   
  
Таким образом мы умеем искать строку максимальной длины, ветвящуюся влево и вправо за <tex>ST+O(N)</tex>.
+
Таким образом мы умеем искать строку максимальной длины, ветвящуюся влево и вправо за <tex>ST+O(n)</tex>.
  
 
==См. также==
 
==См. также==

Версия 22:13, 21 мая 2015

Суффиксный бор — удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является сжатое суффиксное дерево рассматриваемое далее.

Определение

Определение:
Суффиксное дерево (сжатое суффиксное дерево) [math]T[/math] для строки [math]s[/math] (где [math]|s| = n[/math]) — дерево с [math]n[/math] листьями, обладающее следующими свойствами:
  • Каждая внутренняя вершина дерева имеет не меньше двух детей;
  • Каждое ребро помечено непустой подстрокой строки [math]s[/math];
  • Никаких два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа;
  • Дерево должно содержать все суффиксы строки [math]s[/math], причем каждый суффикс заканчивается точно в листе и нигде кроме него.


Суффиксное дерево для строки [math]xabxa[/math] с защитным символом

Данное определение порождает следующую проблему:
Рассмотрим дерево для строки [math]xabxa[/math]: суффикс [math]xa[/math] является префиксом суффикса [math]xabxa[/math], а, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки [math]s[/math] добавляют символ, не входящий в исходный алфавит: защитный символ. Обозначим его как [math]\$[/math]. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т. к. в такой строке не существует двух различных подстрок одинаковой длины, заканчивающихся на [math]\$[/math].

Далее [math]n[/math] — длина строки [math]s[/math] с защитным символом.

Количество вершин

По определению, в суффиксном дереве содержится [math]n[/math] листьев. Оценим количество внутренних вершин такого дерева.

Лемма:
Количество внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества листьев.
Доказательство:
[math]\triangleright[/math]

Докажем лемму индукцией по количеству листьев [math]n[/math].

База

При [math]n = 2[/math] в дереве одна внутренняя вершина, следовательно утверждение верно.

Переход [math]n \rightarrow n + 1[/math]

Возьмем вершину в дереве с [math]n + 1[/math] листами, у которой два ребенка — листья. Рассмотрим возможные случаи:

1) У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с [math]n[/math] листьями, причем в нем количество внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее [math]n[/math] внутренних вершин, а, значит, и для исходного дерева лемма верна.

2) У нее ровно два ребенка. Отрежем их, получим дерево с [math]n - 1[/math] листьями, количество внутренних вершин которого на [math]1[/math] меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее [math]n - 1[/math] внутренних вершин, значит, в исходном дереве их меньше [math]n[/math].
[math]\triangleleft[/math]

Занимаемая память

Представим дерево как двумерный массив размера [math]|V| \times |\Sigma|[/math], где [math]|V|[/math] — количество вершин в дереве, [math]|\Sigma|[/math] — мощность алфавита. Для любого суффиксного дерева верна предыдущая лемма (у каждой вершины, по определению, не менее двух детей), значит, [math]|V| = O(2 n)[/math]. Каждая [math][i][j][/math] ячейка содержит информацию о том, в какую вершину ведет ребро из [math]i[/math]-ой вершины по [math]j[/math]-ому символу и индексы [math]l, r[/math] начала и конца подстроки, записанной на данном переходе. Итак, дерево занимает [math]O(n|\Sigma|)[/math] памяти.

Построение суффиксного дерева

Наивный алгоритм

Рассмотрим наивный алгоритм построения суффиксного дерева строки [math]s[/math]:

go[0] = Vertex() // корень
count = 0 // номер последней вершины, созданной в дереве (глобальная переменная)
for i = 0 to n // для каждого символа строки
    insert(i, n) // добавляем суффикс, начинающийся с него
insert(l, r):
    cur = 0 
    while l < r
        if go[cur][s[l]].v == -1        // если мы не можем пойти из вершины по символу [math] l [/math]
            createVertex(cur, l, r)     // создаем новую вершину 
        else
            start = go[cur][s[l]].l
            finish = go[cur][s[l]].r
            hasCut = false
            for j = start to finish     // для каждого символа на ребре из текущей вершины
                if s[l+j-start] [math] \neq [/math] s[j] // если нашли не совпадающий символ
                    // создаем вершину на ребре
                    old = go[cur][s[l]]
                    createVertex(cur, l, j - 1)
                    go[count][s[j]].v = old
                    go[count][s[j]].r = j
                    go[count][s[j]].l = finish
                    createVertex(count, l + j - start, r)
                    hasCut = true
                    break
            if !hasCut
                cur = go[cur][s[l]].v  // переходим по ребру
                l = l + finish - start // двигаемся по суффиксу на длину подстроки, записанной на ребре
            else
                break
createVertex(cur, l, r):
    go[++count] = Vertex()
    go[cur][s[l]].v = count
    go[cur][s[l]].l = l
    go[cur][s[l]].r = r


Этот алгоритм работает за время [math]O(n^2)[/math], однако алгоритм Укконена позволяет построить сжатое суффиксное дерево за [math]O(n)[/math].

Построение из суффиксного массива

Пусть нам известен суффиксный массив [math]suf[/math] строки [math]s[/math], его можно получить алгоритмом Карккайнена-Сандерса за линейное время. Для преобразования нам также понадобится массив [math]lcp[/math] (longest common prefix), который можно получить алгоритмом Касаи.

В этом преобразовании используется тот же инвариант, что и в других суффиксных структурах:

  1. Строка [math]s[/math] заканчивается специальным символом, который больше не встречается в строке.
  2. Следствие: [math]lcp[i] \lt len[i - 1][/math], где [math]len[i - 1][/math] — длина суффикса, соответствующего [math]suf[i - 1][/math].

Будем строить дерево, добавляя суффиксы в лексикографическом порядке. Чтобы ускорить добавление, будем использовать то, что [math]i[/math]-ый суффикс имеет с предыдущим [math]lcp[i][/math] общих символов. Тогда добавление из корня не отличается от того, что мы поднимемся вверх из предыдущего суффикса до глубины [math]lcp[i][/math] и продолжим построение оттуда. Инвариант позволяет нам утверждать, что ни один лист мы не сможем продолжить, и нам всегда нужно будет хоть раз подняться из него вверх. Поскольку суффиксы отсортированы лексикографически, мы не будем спускаться по ребру после того, как уже поднялись из него из-за несовпадения символа. Все это позволяет сформулировать алгоритм добавления суффикса по известной вершине предыдущего суффикса:

  1. Подняться из вершины вверх до глубины [math]lcp[/math]
  2. Если эта глубина находится на ребре, разрезать ребро по ней.
  3. Вставить новую вершину как сына вершины с глубиной [math]lcp[/math]

В вершинах дерева [math]Node[/math] мы будем хранить предка [math]parent[/math], стек детей в лексикографическом порядке ребер [math]children[/math], глубину вершины в символах от корня [math]depth[/math]. Соответственно, конструктор вершины имеет вид Node(Node parent, int depth).

Node addNextSuffix(Node previous, int length, int lcp):
   if previous.depth == 0 or previous.depth == lcp            // Добавляем к сыновьям текущей вершины 
      added = Node(previous, length)
      previous.children.push(added)
      return added
   else
      if previous.parent.depth < lcp:                          // Нужно разрезать ребро 
         inserted = Node(prevous.parent, lcp)
         previous.parent.children.pop()
         previous.parent.children.push(inserted)
         inserted.children.push(previous)
         previous.parent = inserted
      return addNextSuffix(previous.parent, length, lcp)      
      
Node buildSuffixTree(int[] suf, int[] lcp, int length):
   root = Node(null, 0)
   previous = root
   for i = 1 to length
      previous = addNextSuffix(previous, length - suf[i], lcp[i])
   return root

В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью обхода в глубину посчитаем для каждой вершину дерева максимальную глубину ее листа [math]maxDepth[/math].

Тогда ребро [math]s[start, end][/math] определяется так:

function calculatePositions(Node parent, Node child, int stringLength):
   start = stringLength - child.maxDepth + parent.depth
   end = start + child.depth - parent.depth - 1

Для асимптотического анализа будем использовать в качестве потенциала глубину в вершинах. При добавлении суффикса мы спускаемся один раз, подняться выше корня мы не можем, значит, и подниматься мы будем суммарно [math]O(n)[/math] раз. Обход в глубину также выполняется за [math]O(n)[/math], итоговая асимптотика [math]O(n)[/math].

Использование сжатого суффиксного дерева

Суффиксное дерево позволяет за линейное время найти:

  • Количество различных подстрок данной строки
  • Наибольшую общую подстроку двух строк
  • Суффиксный массив и массив [math]lcp[/math] (longest common prefix) исходной строки
  • Строку максимальной длины, ветвящуюся влево и вправо за [math]ST + O(n)[/math]

Построение суффиксного массива и массива lcp из суффиксного дерева

Пусть к строке дописан специальный символ для сохранения инварианта. Рассмотрим лексикографический по ребрам порядок обхода сжатого суффиксного дерева. Пусть два суффикса имеют общее начало, но различаются в [math]i[/math]-ом символе. Первым будет рассмотрено поддерево по ребру с меньшим символом, значит и лист, соответствующий этому суффиксу, будет посещен первым.

Тогда суффиксный массив строится из суффиксного дерева обходом в глубину в указанном порядке. Пусть длина строки [math]length[/math], глубина листа в символах [math]depth[/math], тогда номер суффикса [math]i = length - depth[/math].

Для заполнения массива [math]lcp[/math] нам понадобится вершина [math]minNode[/math], которая будет означать вершину с минимальной глубиной, в которую мы поднимались при переходе между суффиксами. Поскольку мы точно поднимались туда, но не поднимались выше, это будет наименьший общий предок этих узлов. Из этого следует, что у рассматриваемых суффиксов совпадает ровно [math]lcp = minNode.depth[/math] символов.

int curPos = 0
Node minNode = root
// Для заполнения нужно вызвать dfs(root) 
function dfs(Node n):
   if n.children.size == 0
      suf[curPos] = length - n.depth
      lcp[curPos] = minNode.depth
      curPos++
      minNode = n
   else
      foreach child in n.children
         if n.depth < minNode.depth:
            minNode = n
         dfs(child)

Асимптотика алгоритма совпадает с асимптотикой обхода в глубину и составляет [math]O(n)[/math].

Таким образом, мы умеем за [math]O(n)[/math] строить суффиксное дерево, суффиксный массив и преобразовывать одно в другое.

Поиск строки максимальной длины, ветвящейся влево и вправо

Определение:
Строка [math]s[/math] называется ветвящейся вправо в [math]t[/math] (англ. right merging string), если существуют символы [math]c[/math] и [math]d[/math], такие что [math]c[/math] [math]\ne[/math] [math]d[/math] : [math]sc[/math] и [math]sd[/math] — подстроки [math]t[/math]. Аналогично, ветвящаяся влево (англ. left merging), если [math]cs[/math] и [math]ds[/math] — подстроки [math]t[/math].
Суффиксное дерево для строки [math]aabcabd[/math]

Построим cуффиксное дерево при помощи Алгоритма Укконена. В полученном дереве не листовой вершине [math]v[/math] будет соответствовать подстрока [math]s[/math], которая ветвится вправо, при условии, что количество "хороших" детей вершины [math]v \gt 2[/math] ("хорошие" дети - листы, метка которых [math]\ne\$[/math]). В примере для строки [math]aabcabd[/math] это [math]b[/math], [math]a[/math] и [math]ab[/math]. Далее введём термины левый символ и вершина различная влево, что бы найти строки, ветвящиеся влево.

Определение:
Левый символ для позиции [math]i[/math] строки [math]S[/math] — это символ [math]S(i-1)[/math]. Левым символом листа [math]L[/math] называется левый символ начала суффикса, ведущего в этот лист.


Определение:
Вершина [math]v[/math] различна влево, если как минимум два листа в поддереве [math]v[/math] имеют различные левые символы. По определению лист не может быть различным влево.
Теорема (о строке, ветвящейся вправо и влево):
Строка [math]a[/math], соответствующая пути к вершине [math]v[/math], является ветвящейся вправо и влево тогда и только тогда, когда вершина [math]v[/math] различна влево и счётчик вершины [math]\gt 1[/math].
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow[/math]

Предположим, что [math]v[/math] различна влево. Значит, что существуют подстроки [math]cs[/math] и [math]ds[/math]. Пусть за первой подстрокой следует символ [math]p[/math]. Если за второй подстрокой следует символ, [math]\ne p[/math], то [math]s[/math] - строка, ветвящаяся вправо и влево. Так как у [math]v[/math] есть два различных ребёнка, которые начинаются с различных символов [math]p,q \ne \$[/math], строка является ветвящейся вправо.

[math]\Rightarrow[/math]

Пусть строка [math]s[/math] является ветвящейся вправо и влево. Тогда существуют подстроки [math]csa[/math] и [math]dsb[/math]. В суффиксном дереве существует вершина [math]v[/math] соответствующая строке [math]s[/math] (так как есть как минимум два суффикса, начинающиеся со строки [math]s[/math]). У вершины [math]v[/math], есть как минимум два ребёнка, которые начинаются с символов [math]a[/math] и [math]b[/math] [math]\Rightarrow[/math] счётчик вершины [math]\gt 2[/math]. Так же у вершины [math]v[/math], есть как минимум два ребёнка, у которых левый символ [math]c[/math] и [math]d[/math], значит вершина [math]v[/math] различна влево по определению.
[math]\triangleleft[/math]

Что бы найти строки, ветвящиеся влево, нужно проверить все вершины суффиксного дерева на различность влево. Если какая-то вершина [math]v[/math] будет различна влево и удволетворять свойству ветвимости право, то строка, соответствующая вершине [math]v[/math] будет ветвится вправо и влево по теореме.

Что бы найти вершины различные влево будем хранить левый символ для каждой вершины, пусть он будет [math]\$[/math], если вершина различна влево. Что бы промаркировать всё дерево, нужно записать левые символы для листов, а затем подниматься вверх по дереву. Для каждой вершины [math]v[/math] будем запускать проверку:

  • Если среди левых символов детей [math]v[/math] есть хотя бы один [math]\$[/math], то запишем в [math]v[/math] [math]\$[/math] и закончим проверку.
  • Если среди левых символов детей [math]v[/math] нет ни одного [math]\$[/math], то проверим на совпадение левые символы детей:
    • Если все левые символ детей [math]v[/math] одинаковы и эквивалентны [math]x[/math], то запишем в [math]v[/math] [math]x[/math].
    • Если не все левые символы детей [math]v[/math], то запишем в [math]v[/math] [math]\$[/math] — вершина различна влево.

Так как время проверки [math]v[/math] пропорционально числу детей, время работы всего алгоритма — [math]O(n)[/math].

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

Таким образом мы умеем искать строку максимальной длины, ветвящуюся влево и вправо за [math]ST+O(n)[/math].

См. также

Источники информации

  • Дэн ГасфилдСтроки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.