BWT backward search algorithm is pretty straightforward if we only need the multiplicity of a pattern. However I also need to find the suffix indices (i.e. positions in the reference string where a pattern occurs). e.g., given string banana and pattern an, it occurs twice at positions 1 and 3.
I could compute all suffixes and sort them, but that would increase the time complexity to O(nlogn), n being length of the reference string. Is there a way to do this and still keep the O(length of pattern) time complexity?