title: Text packing algorithm
body: <p>I bet somebody has solved this before, but my searches have come up empty.</p>
  
  <p>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.</p>
  
  <p>Example: doll dollhouse house</p>
  
  <p>These can be packed into the buffer simply as <code>dollhouse</code>, remembering that <code>doll</code> is four letters starting at position 0, <code>dollhouse</code> is nine letters at 0, and <code>house</code> is five letters at 3.</p>
  
  <p>What I've come up with so far is:</p>
  
  <ol>
  <li>Sort the words longest to shortest:  (dollhouse, house, doll)</li>
  <li>Scan the buffer to see if the string already exists as a substring, if so note the location.</li>
  <li>If it doesn't already exist, add it to the end of the buffer.</li>
  </ol>
  
  <p>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 <code>dollhouseragdoll</code> which is less efficient than <code>ragdollhouse</code>.</p>
  
  <p>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.</p>
  
  <p>As a side note, this storage scheme is used for the data in the `name' table of a TrueType font, cf. <a href="http://www.microsoft.com/typography/otspec/name.htm" rel="nofollow noreferrer">http://www.microsoft.com/typography/otspec/name.htm</a></p>