Алгоритм нахождения длины самого длинного суффикса между строкой и префиксом строки
Входные данные :
Есть длинная строка S и у нас есть массив целых A который обозначает префиксы строки S лайк A[i] обозначает префикс S[0..A[i]]
Выход:
Вернуть массив Output[] того же размера, что и A где Output[i] длина самого длинного соответствующего суффикса S[0..A[i]] а также S
Пример ввода:
S = "ababa"
A[]=[0, 1, 2, 3, 4]
Пример вывода:
Output[]=[1,0,3,0,5]
Самый наивный алгоритм, который у меня есть, для каждого A[i] просто сопоставьте количество символов между S[0..A[i]] а также S с конца обеих строк. Но этот алгоритм O(n^2) где n - длина исходной строки S.
Вопрос:
Есть ли лучший алгоритм, который предварительно обрабатывает строку S, а затем может быстро вернуть самый длинный суффикс длины для всего входного массива?
2 ответа
Это просто Z-функция обратной строки. Небольшое отличие состоит в том, что первый элемент Z-функции выбран равным длине S. Существует алгоритм для вычисления Z-функции строки в O(n)
И алгоритм для этой проблемы заключается в следующем:
- S': = обратный S
- Z: = Z-функция S'
- для каждого i выведите [i]:= Z[Len(S) - A[i] - 1]
Например:
S = "baabaaa"
A[] = [0,1,2,3,4,5,6]
Output[] should be [0,1,2,0,1,2,7]
S' = "aaabaab"
Z = Z-function(S') = [7,2,1,0,2,1,0] (with the first element chosen to be Len(S))
Алгоритм / структура данных, которую вы ищете, называется Suffix Tree, в худшем случае имеет сложность O(n log n)
В компьютерных науках дерево суффиксов (также называемое деревом PAT или, в более ранней форме, деревом позиций) представляет собой сжатый файл, содержащий все суффиксы данного текста в качестве их ключей и позиции в тексте в качестве своих значений. Суффикс-деревья обеспечивают особенно быструю реализацию многих важных строковых операций. ( вики)
Здесь вы можете найти несколько слайдов, которые подробно объясняют функциональность и реализацию