To find the k-best matches for a particular substring s, we do what we would normally do for standard suffix arrays on lexicographic splits.
on popularity splits, we search the more popular half first and then we search the less popular half, if necessary.