EPR-dictionaries: A practical and fast data structure for constant time searches in unidirectional and bidirectional FM-indices

Christopher Pockrandt, Marcel Ehrhardt, Knut Reinert

We introduce a new, practical method for conducting an exact search in a uni- and bidirectional FM index in $O(1)$ time per step while using $O(\log \sigma \ast n)+o(\log \sigma \ast \sigma \ast n)$ bits o…