= Solution
Use one-based row numbers, and write $F$ and $L$ for the first and last columns. The <last-to-first mapping> matches the $k$th occurrence of a character in $L$ to its $k$th occurrence in $F$: equal characters retain the ordering of their following suffixes. This lets us extend an interval of matching <suffixes> one character to the left without reconstructing the full strings.
Start with the last query character. Rows $5,6,7$ of $F$ contain C, so the interval of <suffixes> beginning with C is $[5,7]$. Within those rows, the A entries of $L$ are at rows $5$ and $7$. They are respectively the first and second A entries in all of $L$, and therefore map to rows $2$ and $3$ of $F$. These are exactly the <suffixes> beginning with AC. Reading their supplied positions gives \b[matches starting at positions 11 and 3], or positions \b[3 and 11] in increasing genomic order.
The same calculation can be written as <backward search>. Let $C(c)$ count characters strictly smaller than $c$, and let $\operatorname{Occ}(c,r)$ count occurrences of $c$ in $L[1:r]$, with $\operatorname{Occ}(c,0)=0$. Prepending $c$ changes an inclusive interval $[l,r]$ to
$$
[l',r']=[C(c)+\operatorname{Occ}(c,l-1)+1,\ C(c)+\operatorname{Occ}(c,r)].
$$
Here $C(\mathrm A)=1$, $\operatorname{Occ}(\mathrm A,4)=0$ and $\operatorname{Occ}(\mathrm A,7)=2$, giving $[l',r']=[2,3]$.
Back to article page
