It seems to skip a lot for substring search. For example if you search for 'aaaa' there's maybe 100 jumps to get to the bottom. So i'd assume that it's just a uniform random over the entire range to some limit, then filter idx > cur. But I feel like you could constrain the search more. The 'close next' should have exactly the same characters at the front. Like in your example '4AAB-' you would search valid position 14 first.

edit: actually this doesn't work because having the same start does not mean they are close together.