СПОСОБ НАХОЖДЕНИЯ МАКСИМАЛЬНЫХ ПОВТОРЯЮЩИХСЯ УЧАСТКОВ ПОСЛЕДОВАТЕЛЬНОСТИ СИМВОЛОВ КОНЕЧНОГО АЛФАВИТА И СПОСОБ ВЫЧИСЛЕНИЯ ВСПОМОГАТЕЛЬНОГО МАССИВА

1
1
1
1
1
1. Способ нахождения максимальных участков в конечной последовательности символов x[i] (0≤i<N) конечного алфавита, являющихся повторениями ранее встречавшихся участков, при котором вычисляют последовательность s[i] по всем N значениям индексов i (0≤i<N), где s[i] - максимальная длина линейного участка указанной последовательности данных, индекс начального элемента которого совпадает с данным индексом i, совпадающего с некоторым другим участком той же последовательности данных x[i], начало которого расположено ближе к началу последовательности данных x[i], чем начало указанного линейного участка, после чего определяют все указанные максимальные участки как все отрезки x[m,n] последовательности x[i], для которых начальный индекс m удовлетворяет условию s[m]>s[m-1]-1, а конечный индекс n равен m+s[m]-1.
2. Способ по п.1, в котором совокупность всех указанных максимальных участков кодируют двумя битовыми массивами beg[i] и end[i], где единичное значение i-го элемента означает, что i-я позиция в указанной последовательности является соответственно началом и концом некоторого максимального указанного участка.
2
2
2
2
2
3. Способ по п.2, в котором для вычисления указанных битовых массивов вычисляют последовательность s[i] по всем N значениям индексов i (0≤i<N), где s[i] - максимальная длина линейного участка указанной последовательности данных, индекс конечного элемента которого совпадает с данным индексом i, совпадающего с некоторым другим участком той же последовательности данных x[i], конец которого расположен ближе к началу последовательности данных x[i], чем конец указанного линейного участка, после чего определяют все указанные максимальные участки как все отрезки x[m,n] последовательности x[i], для которых конечный индекс n удовлетворяет условию s[n]>s[n+1]-1, а начальный индекс m равен n-s[n]+1.
2
2
2
2
4. Способ вычисления массива всех значений функции s[i] для всех N значений индексов i (0≤i<N), где s[i] - максимальная длина линейного участка заданной последовательности символов x[i], индекс конечного элемента которого совпадает с данным индексом i, совпадающего с некоторым другим участком той же последовательности данных x[i], конец которого расположен ближе к началу последовательности данных x[i], чем конец i указанного линейного участка, с помощью компьютерной реализации алгоритма Укконена, при котором для каждой i-й фазы алгоритма Укконена после определения канонической ссылочной пары (s,k) активного суффикса вычисляют s[i] как длину активного суффикса, равную s[i]=i-j-k+1, где j - позиция начала активного суффикса, хранящаяся в узле s суффиксного дерева, которое построено для префикса строки x[i], включающего в себя первые i символов указанной последовательности.