A Simple Algorithm for Computing the Document Array
arXiv:1812.09094 · doi:10.1016/j.ipl.2019.105887
Abstract
We present a simple algorithm for computing the document array given a string collection and its suffix array as input. Our algorithm runs in linear time using constant additional space for strings from constant alphabets.