StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If you want to do this once, I'd do the following (generalized to the problem of starting with a full word):</p> <p>Take your entire dictionary and throw away anything that does not have a superset of the characters in your target word (let's say it has length <code>m</code>). Then bin the remaining words by length. For each word of length <code>m+1</code>, try dropping each letter and see if that yields your desired word. If not, toss it. Then check each word of length <code>m+2</code> against the valid set of length <code>m+1</code>, dropping any that can't be reduced. Keep going until you find an empty set; the last thing(s) you found will be the longest.</p> <p>If you want to make this fast to look up, I'd build a suffix-tree-<em>like</em> data structure.</p> <p>Group all words by length. For each word of length 2, place each of its two characters in a "subword" set, and add that word to each of the characters' "superword" sets. Now you've got a link between all valid words of length 2 and all characters. Do the same with words of length 3 and valid words of length 2. Now you can start anywhere in this hierarchy and do a breadth-first search to find the deepest branch.</p> <hr> <p>Edit: the speed of this solution will depend greatly on the structure of the language, but if we decide to build everything using sets with <code>log(n)</code> performance for all operations (i.e. we use red-black trees or the like), and we have <code>N(m)</code> words of length <code>m</code>, then to form the link between words of length <code>m+1</code> and <code>m</code> will approximately <code>(m+1)*m*N(m+1)*log(N(m))</code> time (taking into account that string compares take linear time in the length of the string). Since we have to do this for all word lengths, the runtime for building the full data structure will be something on the order of</p> <pre><code>(typical word length)^3 * (dictionary length) * log (dictionary length / word length) </code></pre> <p>(The initial binning into words of a certain length will take linear time so can be neglected; the actual formula for runtime is complicated because it depends on the distribution of word lengths; for the case where you're doing it from a single word it's even more complicated because it depends on the expected number of longer words that have shorter subwords.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload