Text indexing is fundamental to many areas in Computer Science such as Information Retrieval, Bioinformatics, etc. The primary goal here is to preprocess a long text T[1, n] (given in advance), such that whenever a shorter pattern P[1, m] comes as query, all occ occurrences (or simply, starting positions) of P in T can be reported efficiently. Such queries can be answered in optimal O(m + occ) time using the classic Suffix tree data structure [1, 2]. It takes O(n) words of space. In this paper, we focus on a variation of the text indexing problem, known as the non-overlapping indexing, which is central to data compression [3, 4].

Problem 1 (Non-overlapping Indexing). Preprocess a text T[1, n] into a data structure that supports the following query: given a pattern P[1, m], report a largest set of occurrences of P in T (denote its size by nocc), such that any two (distinct) text positions in the output are separated by at least m characters.