= Backward search
<Backward search> finds a query's matching interval in a <suffix array> by processing the query from right to left. With inclusive one-based interval $[l,r]$, prepending $c$ changes it to $[C(c)+\operatorname{Occ}(c,l-1)+1,C(c)+\operatorname{Occ}(c,r)]$. An empty interval means no match. This works through the occurrence-order property of the <last-to-first mapping>.<Opportunistic Data Structures with Applications by Paolo Ferragina and others>[§3.1, Figure 1, BW Search]{ref}
Back to article page
