[31] Let I be an index structure supporting text search in O(l(P))-bit probes to find pattern P in text T as a substring.

(a) If each query requires the location of P, then the size of I is Ω(l(T )).

(b) Even if each query asks only whether a substring P is in T , the size of I is still Ω(l(T )).

Comments. Item

(a) is by E.D. Demaine and A. Lopez-Ortiz [J. Alg., 48:1(2003), 2–15]. Item

(b) is due to M. Li and P.M.B. Vit´anyi [Unpublished, 2006]. Hint for Item (b): use Lemma 6.9.2.

An upper bound of Item

(b) is O(w log N) bits for w query words, by M.L. Fredman, J.

Koml´os, and E. Szemer´edi [J. Assoc. Comp. Mach. 31:3(1984), 538–544].