```"Tobias Reif" <tobiasreif / pinkjuice.com> wrote in,
....

> Hi;
>
> Better than Superbowl, bigger than the Olympics;

Hm, the Olympics are winding and I got some time on my hand.  I was
always wandering if this particularly idea was at all practical - the algorithm
does not guaranty that you found a longest match but the changes that you
are about as likely as a snowball in hell - There are plenty of variations
of this idea and a C-based implementation would probably be pretty fast.
Anyway,  the ratio of the running times of my scripts (which requires a cvs
version) and Daves addagram  is  ~ 0.7 ...

/Christoph

-----
class String

#   Original ordering - the fact that the larger number are primes probably
#   makes no difference for the smaller it certainly does
#
#    tmp =[2, 5,13,23,53,113,257,569,1249,2749,6089,13441,29683,65537,
#              144719,319567,705643,1558177,3440719,7597757,16777213,
#              37047091,81806611,180643669,398893589,880828517]
#
#    Ordered by hand  - I didn't put a lot of thought into this ...

tmp =[180643669, 5,13,705643 ,81806611,113,257,569, 37047091,2749,
6089,13441,29683,65537,7597757,319567, 23 ,1558177,3440719,
144719,16777213, 1249, 53,  2, 398893589,880828517]

#   This particularly ordering results in two #ab_hash collisions  -
#    "brownish", "forgings"  and  "fogginess", "wishbones"

PTable = Array.new(65).concat(tmp.dup.concat(Array.new(6).concat(tmp)))

def ab_hash
hsh = 0
each_byte { |byte| hsh+=  PTable[byte] }
hsh
end
def ab_eql?(other)
unpack("c*").sort.pack("c*") == other.unpack("c*").sort.pack("c*")
end
end

class LArray < Array
class NAHash < Hash
def sol(hsh)
return [ fetch(hsh) { return nil } ]
end
def solution
length.zero?  ?  nil : [to_a[0][1]]
end
end
class AHash < NAHash
PTable = String::PTable
RTable = Array.new(65).concat(('A'..'Z').collect{|i| Regexp.new(i)}.\
concat(Array.new(6).concat(('a'..'z').\
collect{|i| Regexp.new(i)})))
# the RTable stuff does not buy you all that much ...
def sol(hsh)
wrd = fetch(hsh) {return nil}
wrd.each_byte do |byte|
if (res = @prev.sol(hsh- PTable[byte]))  && \
# res[0].ab_eql?(wrd.sub(/#{byte.chr}/,''))
res[0].ab_eql?(wrd.sub(RTable[byte],''))
return res.unshift(wrd)
end
end
delete(hsh)
return nil
end
def initialize(prev)
@prev = prev
end
def solution
each do |hsh,wrd|
wrd.each_byte do |byte|
if (res = @prev.sol(hsh- PTable[byte]))  && \
# res[0].ab_eql?(wrd.sub(/#{byte.chr}/,''))
res[0].ab_eql?(wrd.sub(RTable[byte],''))
return res.unshift(wrd)
end
end
end
return nil
end
end
def initialize(len)
super(len)
self[3] = NAHash.new
for i in 4...len do self[i] = AHash.new(self[i-1]) end
end
def solution
(length-1).downto(0) do |i|
if res = self[i].solution
return res
end
end
end
end

table = LArray.new(30)
table[wrd.length][wrd.ab_hash] = wrd unless wrd.length < 3
end
puts table.solution

=begin
which might result in

underestimations
underestimation
determinations
antimodernist
terminations
nitrosamine
antinomies
nominates
misatone
atonies
tisane
anise
sine
sen
=end
----

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/2002

```