pipette
ESEspañol

Substring Complexity in BWT-Runs Bounded Space

Johannes Fischer

Preprint

In the authors' words

Given a string , its substring complexity is defined as , where is the number of its distinct substrings of length in . We show how to compute it in time, using only words of space, where denotes the number of runs in the Burrows-Wheeler transform.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.