On Minimal and Maximal Suffixes of a Substring

Lecture Notes in Computer Science. 2013. Vol. 7922. P. 28–37.

Maxim Babenko, Ignat Kolesnichenko, Стариковская Т. А.

Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string S can be computed in linear time and space by constructing a suffix tree or a suffix array of S. Here we consider the case when S is a substring of another string T of length n.We propose two linear-space data structures for T which allow to compute the minimal suffix of S in O(log^1+ε n) time (for any fixed ε > 0) and the maximal suffix of S in O(log n) time. Both data structures take O(n) time to construct.

Ключевые слова: lexicography, suffixes, substring, stringology