Scan every time, or build the index once

Scan every time, or build the index once

A text of 4,096 characters over 4 symbols. Building the suffix array by prefix doubling and its LCP array by Kasai's method costs 8,188 character comparisons and 85,248 integer comparisons, paid once. After that a query costs 89 characters against a scan's 1739. The lines cross at 5 queries, which is the whole of the decision.

Drawn at 700 × 430, wide on the page. Everything above is what suffix-index returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

3 essays call suffix-index. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.