Самые длинные общие префиксы

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

Пример: для строки str=abcabbca,

массив суффиксов:

suffixArray[] = [7 3 0 4 5 1 6 2]

Объяснение:

i   Suffix      LCP of str and str[i..]   Length of LCP
7   a           a                           1
3   abbca       ab                          2
0   abcabbca    abcabbca                    8
4   bbca        empty string                0
5   bca         empty string                0
1   bcabbca     empty string                0
6   ca          empty string                0
2   cabbca      empty string                0

Теперь, когда построено это suffixArray, я хочу найти длину самого длинного общего префикса (LCP) между str (самой строкой) и каждым другим суффиксом. Каков наиболее эффективный способ сделать это?


algorithm suffix-array
person Ritesh Kumar Gupta    schedule 17.06.2012    source источник
comment
Можем ли мы предположить, что вы также построили стандартный массив LCP, т. е. такой массив, что LCP[i] = самый длинный общий префикс SA[i] и SA[-1]? Он часто создается как часть построения массива суффиксов.   -  person jogojapan    schedule 19.06.2012
comment
Да, я построил стандартный массив LCP.   -  person Ritesh Kumar Gupta    schedule 19.06.2012

Ответы (1)


arrow_upward
4
arrow_downward

Основываясь на вашем комментарии, я предполагаю, что у нас есть доступ к массиву суффиксов SA, а также к стандартному массиву LCP, то есть к структуре данных, которая сообщает нам при индексе i>0, какова длина самого длинного общего префикса суффикса SA[i]. и его лексикографический предшественник SA[i-1] есть.

Я буду использовать букву L для обозначения специального массива LCP, который мы хотим построить, как описано в вопросе. Я буду использовать букву N для обозначения длины входной строки str.

Тогда что мы можем сделать, так это:

  1. Определите положение str в массиве суффиксов. Мы можем сделать это, просматривая SA линейно, чтобы найти запись 0. (Пояснение: str — это суффикс str, начинающийся с позиции 0. Следовательно, 0 должен отображаться как элемент массива суффиксов.)

  2. Предположим, что запись, которую мы нашли, имеет индекс k. Тогда мы можем установить L[k]:=N, потому что SA[k] это сама строка и имеет общий с собой префикс из N символов.

  3. Затем мы можем установить L[k-1]:=LCP[k] и L[k+1]:=LCP[k+1], потому что именно так определяется стандартная LCP.

  4. Затем мы идем назад от i:=k-2 вниз к 0 и устанавливаем

    L[i] := min(LCP[i+1],L[i+1])

    Это работает, потому что на каждой итерации i LCP[i+1] сообщает нам самый длинный общий префикс соседних суффиксов SA[i] и SA[i+1], а L[i+1] сообщает нам самый длинный общий префикс ранее обработанного суффикса SA[i+1] и входной строки str. L[i] должно быть минимальным из этих двух, потому что L[i] указывает, как долго префикс SA[i] имеет общее с str, и это не может быть длиннее префикса, общего с SA[i+1], иначе его позиция в массиве суффиксов была бы ближе к k .

  5. Мы также считаем вперед от i:=k+2 до N и устанавливаем

    L[i] := min(LCP[i],L[i-1])

    исходя из тех же соображений.

Затем были установлены все N значений L, и это заняло не более O(N) времени, если предположить, что произвольный доступ к массивам и целочисленное сравнение составляют O(1) соответственно.

Поскольку массив, который мы вычисляем, имеет длину N элементов, оптимальной является сложность O(N).

(Примечание. Вы можете начать циклы в шагах 4 и 5 с k-1 и k+1, соответственно, и избавиться от шага 3. Дополнительный шаг служит только для того, чтобы объяснить - надеюсь - немного легче следовать.)

person jogojapan    schedule 19.06.2012
comment
: Большое спасибо, это именно то, что я хотел .. :) - person Ritesh Kumar Gupta; 19.06.2012