My first job out of school was writing a spell checker/auto completion system. If you want to weigh predictions by the expected number of keystrokes saved. This is a bit like the opposite problem, find the longest word D that is a supersequence of S (You want to find them all, to weigh by probability), but would essentially be solved with the same data structures. I assume that this sort of problem is not particularly rare, and is unlike sorting in that it's not quite as universal, and the one line function doesn't live in the standard library, or any package that I could find. The fact that the algorithms were still fresh in my mind helped immensely.