Support offsets in prefix searching

Fixes T75522
Change-Id: I7a27a64e295a1efcb1d9728d95cf254bb8bfbe92