FIX to A Self-Index on Block Trees

Level: Medium

To find the primary occurrences, the paper says in Sec. 3.1. we have to index the suffix S[j..n], but this may lead to duplicate reporting of the same occurrence, found at different offsets k at different levels.

To avoid this, we must index only S[j..j+b_l-1], except for the blocks at level 0, where we must actually index the whole suffixes. Thus, for each block that splits in two, we index the left part reversed and the right part not reversed, apart from indexing the root blocks with their following suffixes. We can know the length of an indexed block, at the time of binary searching, by considering its position: if j is a multiple of 2^y, then its length is 2^y.

A corrected version is already arxived.