Improvement of Practical Suffix Sorting Algorithm
Tae-Young Jeong, Tae‐Hyung Lee, Kun-Soo Park · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2009
The suffix array is a data structure storing all suffixes of a string in lexicographical order. It is widely used in string problems instead of the suffix tree, which uses a large amount of memory space. Many researches have shown that not only the suffix array can be built in O(n), but also it can be constructed with a small time and space usage for real-world inputs. In this paper, we analyze a practical suffix sorting algorithm due to Maniscalco and Puglisi [1], and we propose an efficient algorithm which improves Maniscalco-Puglisi's running time.