Редактирование: Алгоритм МакКрейта

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 6: Строка 6:
 
== Теоретическое обоснование ==
 
== Теоретическое обоснование ==
 
Рассмотрим строку <tex>s</tex> длины <tex>n</tex>, которая заканчивается специальным символом, не встречающимся больше в строке.
 
Рассмотрим строку <tex>s</tex> длины <tex>n</tex>, которая заканчивается специальным символом, не встречающимся больше в строке.
Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше. Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j \ldots n]</tex> и <tex>s[i \ldots n]</tex> среди всех <tex>j < i</tex>.  
+
Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше. Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j..n]</tex> и <tex>s[i..n]</tex> среди всех <tex>j < i</tex>.  
  
 
Пусть мы знаем <tex>head_i</tex> и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать <tex>head_i</tex> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
 
Пусть мы знаем <tex>head_i</tex> и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать <tex>head_i</tex> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
Строка 12: Строка 12:
 
{{Лемма
 
{{Лемма
 
|id=lemma_head
 
|id=lemma_head
|statement=Пусть <tex>head_i = s[i \ldots i+h]</tex>, тогда <tex>s[i+1 \ldots i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.
+
|statement=Пусть <tex>head_i = s[i..i+h]</tex>, тогда <tex>s[i+1..i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.
 
|proof=
 
|proof=
 
* При <tex>h=0</tex>, очевидно, пустая строка является префиксом любой другой.
 
* При <tex>h=0</tex>, очевидно, пустая строка является префиксом любой другой.
* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j \ldots n]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i \ldots n]</tex>. Тогда <tex>s[j+1 \ldots n]</tex> будет иметь с <tex>s[i+1 \ldots n]</tex> общий префикс длины <tex>h-1</tex>. Поскольку любой общий префикс будет по определению также являться и префиксом <tex>head_{i+1}</tex>, получаем искомое утверждение.
+
* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j..n]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i..n]</tex>. Тогда <tex>s[j+1..n]</tex> будет иметь с <tex>s[i+1..n]</tex> общий префикс длины <tex>h-1</tex>. Поскольку любой общий префикс будет по определению также являться и префиксом <tex>head_{i+1}</tex>, получаем искомое утверждение.
 
}}
 
}}
  
Строка 44: Строка 44:
 
|statement=Инвариант алгоритма сохраняется
 
|statement=Инвариант алгоритма сохраняется
 
|proof=Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для <tex>head_{i-1}</tex>, но мы продолжили бы сканирование по ребру дальше и получили две вершины <tex>head_{i-1}.suf,\ head_i</tex> с неопределенными суффиксными ссылками.  
 
|proof=Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для <tex>head_{i-1}</tex>, но мы продолжили бы сканирование по ребру дальше и получили две вершины <tex>head_{i-1}.suf,\ head_i</tex> с неопределенными суффиксными ссылками.  
Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j \ldots n],\ j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1 \ldots n]</tex>. Тогда и <tex>s[i \ldots n]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
+
Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j..n],\ j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1..n]</tex>. Тогда и <tex>s[i..n]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
 
}}
 
}}
  
Строка 50: Строка 50:
 
В вершинах дерева <tex>Node</tex> будем хранить следующую информацию:
 
В вершинах дерева <tex>Node</tex> будем хранить следующую информацию:
 
* <tex>parent</tex> {{---}} предок
 
* <tex>parent</tex> {{---}} предок
* <tex>start, end</tex> {{---}} метка подстроки <tex> s[start \ldots end] </tex> на ребре от предка
+
* <tex>start, end</tex> {{---}} метка подстроки <tex> s[start..end] </tex> на ребре от предка
 
* <tex>length = end - start + 1</tex> {{---}} длина ребра до предка
 
* <tex>length = end - start + 1</tex> {{---}} длина ребра до предка
 
* <tex>depth</tex> {{---}} глубина вершины в символах
 
* <tex>depth</tex> {{---}} глубина вершины в символах

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: