3

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?

John Doe
  • 206
  • 1
  • 6
user798275
  • 131
  • 2

2 Answers2

1

The algorithm you are looking for is Ukkonen's suffix tree. It runs in O(n).

The algorithm you describe is not O(n log n). It has that number of string comparisons. In the extreme case, where your string being is "verylong_verylong_", comparisons take O(n), bringing your algorithm down to quadratic complexity.

Community
  • 1
Franky
  • 129
  • 5
0

BW Transformed text has operations like a linked list, where you can traverse forwards and backwards from each entry to recover the adjacent characters, but finding their offset from the beginning or end requires traversing the whole distance, or attaching information to some or all of the nodes to help determine their offsets.

Any scheme that works for labelling the indices of a linked list will also work for the BWT. For instance, labelling every k-th node, or labelling nodes of a certain type (eg all the n's in the text).

You can also label each node with one bit from a self-framing code. An example is Zeckendorf encoding, which never has two 1 bits in a row, except at code word boundaries. Given a random node, you traverse forward or backwards until you find a word boundary, then read to the next word boundary and decode the bits in between to get the offset.

KWillets
  • 101