Изменения

{{В разработке}}'''Алгоритм МакКрейта''' (англ. ''McCreight's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. Отличается от [[Алгоритм Укконена| алгоритма Укконена]] тем, что добавляет суффиксы в порядке убывания длины. ==Историческая справка==Первым оптимальным по времени был алгоритм, предложенный Вайнером в 1973 году. Идея алгоритма была в нахождении первых символов суффикса, которые находились в уже построенном дереве. Суффиксы просматривались от самого короткого к самому длинному, а для быстрого поиска использовались по два массива размера алфавита на каждую вершину, что затрудняло как понимание алгоритма, так и его реализацию и эффективность, особенно в плане занимаемой памяти. МакКрейт в 1976 году предложил свой алоритм<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.8022&rep=rep1&type=pdf Edward M. McCreight {{---}} A Space-Economical Suffix Tree Construction Algorithm]</ref>, в котором порядок добавления суффиксов заменен на обратный, а для быстрого вычисления места, откуда нужно продолжить построение нового суффикса, достаточно суффиксной ссылки в каждой вершине. В 1995 году Укконен представил свою версию алгоритма<ref>[http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf Esko Ukkonen {{---}} On-line construction of suffix trees]</ref>, которая считается наиболее простой для понимания, а также, в отличие от алгоритмов Вейнера и МакКрейта, является online алгоритмом, способным строить неявное суффиксное дерево по мере прочтения строки, а затем превратить его в настоящее.

Рассмотрим строку <tex>s</tex> длины <tex>n</tex>, которая заканчивается специальным символом, не встречающимся больше в строке.Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше.  {{Определение|id=def_head. |definition=Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j..\left\vert s \right\vertldots n]</tex> и <tex>s[i..\left\vert s \right\vertldots n])</tex> среди всех <tex>j < i</tex>.}}

Пусть мы знаем <tex>head_i</tex> и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать <tex>head_i</tex> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.

|statement=Пусть <tex>head_i = s[i..\ldots i+h]</tex>, тогда <tex>s[i+1..\ldots i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.

* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j..\left\vert s \right\vertldots n]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i..\left\vert s \right\vertldots n]</tex>. Тогда <tex>s[j+1..\left\vert s \right\vertldots n]</tex> будет иметь с <tex>s[i+1..\left\vert s \right\vertldots n]</tex> общий префикс длины <tex>h-1</tex>. Поскольку любой общий префикс будет по определению также являться и префиксом <tex>head_{i+1}</tex>, получаем искомое утверждение.

Если нам известны суффиксные ссылки <tex>u.suf</tex> для каждой вершины <tex>u</tex>, мы можем быстро перейти от позиции <tex>head_i</tex> к ее её суффиксу и продолжить сравнение символов оттуда. Если бы новая позиция <tex>head_i</tex> всегда оказывалась существующей вершиной построенного дерева, этот алгоритм бы уже работал, но в реальности можно оказаться на середине ребра, для которой суффиксная ссылка неизвестна. Для нахождения ее её суффиксной ссылки на следующей итерации мы сначала перейдем к предку, пройдем по суффиксной ссылке, а уже затем будем продолжать сравнение.

* Для любого символа <tex>c</tex> из вершины <tex>superRoot</tex> есть ребро в корень<tex>root</tex>.

*# Поднимемся вверх к ее её предку;

|proof=Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для <tex>head_{i-1}</tex>, но мы продолжили бы сканирование по ребру дальше и получили две вершины <tex>head_{i-1}.suf, \ head_i</tex> с неопределенными суффиксными ссылками. Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j..\left\vert s \right\vertldots n], \ j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1..\left\vert s \right\vertldots n]</tex>. Тогда и <tex>s[i..\left\vert s \right\vertldots n]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.

''Fast scanning'' работает с целыми ребрамирёбрами, поэтому будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. Из структуры [[Сжатое суффиксное дерево| суффиксного дерева]] мы знаем, что суффиксная ссылка может уменьшить глубину вершины не более, чем на <tex>1</tex>, так что мы на каждой итерации поднимаемся не более, чем на <tex>2</tex> {{---}} один раз к предку, а потом по суффиксной ссылке, что составляет <tex>O(n)</tex> за весь алгоритм. Соответственно, спустимся мы тоже суммарно <tex>O(n)</tex> раз, так как и максимальная глубина составляет <tex>O(n)</tex>.

Является первым асимптотически оптимальным В сравнении с алгоритмомВайнера:* Преимущества: каждая вершина хранит только суффиксную ссылку, а не массивы размера алфавита. * Недостатки: нет. В сравнении с [[Алгоритм Укконена| алгоритмом Укконена]]: