Deterministic Indexing for Packed Strings

Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen

Given a string $S$ of length $n$, the classic string indexing problem is to preprocess $S$ into a compact data structure that supports efficient subsequent pattern queries. In the…