Grow words from fertile vocabularies An incremental word chain is a sequence of words of a vocabulary such that each word is the result of either prepending or appending a single character to the previous word, ignoring capitalization. An example of such a chain can be found below.


  I → is → his → hiss


Your task is to write a program that for a given vocabulary finds the longest incremental word chain. The input is provided from standard input a vocabulary as one word per line. The words are composed of the lowercase letters a to z only. The output of your program shall go to standard output and shall be one word per line a longest word chain of the input vocabulary, starting with the shortest word.

This is code golf, the solution with the least character count wins. Different forms of input or output are not possible, but the terms standard input and standard output may be interpreted in a reasonable way for the language you are solving this problem in.

Please demonstrate that your code works by publishing the longest word chain you find on the xz-compressed vocabulary found here. This vocabulary was generated by executing the following series of commands on the file british-english-insane from the SCOWL project in the C locale:

tr 'A-Z' 'a-z' &lt;british-english-insane | sed -n '/^[a-z]*$/p' | sort -u | xz -9e &gt;voc.xz


A solution in polynomial time is possible and highly appreciated.
Ruby, 127

Runs in about 6.5 seconds. Uses a couple of cool tricks. ARGF ($&lt; or stdin, really) is enumerable! If an array is passed as a block argument, it can be "exploded" and assigned to a parameter using {|w,| ... }. Notice the comma.

I found an even shorter solution which uses Array#&amp; (set intersection) to do the lookup of words, but that runs extremely slow, unfortunately.

Thanks to w0lf for shaving off a few characters

D={}
$&lt;.map{|l|D[l.strip!]=l}
puts D.map{|w,|c=[w]
w.chars.all?{w=c[0]
r=D[w.chop]||D[w[1..-1]]
r ?c=[r]+c :p}
c}.max_by &amp;:size


Output

r
ra
rah
rahm
brahm
brahma
brahman
brahmani
brahmanis
brahmanism
brahmanisms


Readable version

D = {}
$&lt;.lines { |l| D[l.strip] = l.strip }

chains = D.map do |word, _|
  chain = [word]

  word.chars.all? do
    word   = c.first
    result = D[w.chop] || D[w[1..-1]]

    result ? chain.unshift(result) : nil
  end
end

puts chains.max_by(&amp;:size)