I bet somebody has solved this before, but my searches have come up empty.
I want to pack a list of words into a buffer, keeping track of the starting position and length of each word. The trick is that I'd like to pack the buffer efficiently by eliminating the redundancy.
Example: doll dollhouse house
These can be packed into the buffer simply as
dollhouse, remembering that
doll is four letters starting at position 0,
dollhouse is nine letters at 0, and
house is five letters at 3.
What I've come up with so far is:
- Sort the words longest to shortest: (dollhouse, house, doll)
- Scan the buffer to see if the string already exists as a substring, if so note the location.
- If it doesn't already exist, add it to the end of the buffer.
Since long words often contain shorter words, this works pretty well, but it should be possible to do significantly better. For example, if I extend the word list to include ragdoll, then my algorithm comes up with
dollhouseragdoll which is less efficient than
This is a preprocessing step, so I'm not terribly worried about speed. O(n^2) is fine. On the other hand, my actual list has tens of thousands of words, so O(n!) is probably out of the question.
As a side note, this storage scheme is used for the data in the `name' table of a TrueType font, cf. http://www.microsoft.com/typography/otspec/name.htm