From: dblack@...
Date: 2006-11-25T08:56:37+09:00
Subject: Re: [QUIZ] DictionaryMatcher (#103)

Hi --

On Sat, 25 Nov 2006, Ruby Quiz wrote:
>
> by Ken Bloom
>
>> From time to time someone asks on ruby-talk how they can write a regexp of the
> form:
>
> 	/alligator|crocodile|bear|dinosaur|...|seven-thousandth-word/
>
> It's not hard to write such a regexp, but Ruby has in internal limit on how big
> the regular expression can be, so users find they can't do this matching
> function easily.
>
> Implement a class DictionaryMatcher that determines whether any of the strings
> added to it are substrings of a string S. This should function as almost a
> drop-in replacement for a Regexp, therefore your implementation should support
> the following operations:
>
> 	# creates a new empty matcher
> 	dm=DictionaryMatcher.new
>
> 	# adds strings to the matcher
> 	dm << "string"
> 	dm << "Ruby"
>
> 	# determines whether a given word was one of those added to the matcher
> 	dm.include?("Ruby")                 # => true
> 	dm.include?("missing")              # => false
> 	dm.include?("stringing you along")  # => false
>
> 	# Regexp-like substing search
> 	dm =~ "long string"            # => 5
> 	dm =~ "rub you the wrong way"  # => nil
>
> 	# will automatically work as a result of implementing
> 	# DictionaryMatcher#=~ (see String#=~)
> 	"long string" =~ dm  # => true
>
> 	# implement the rest of the interface implemented by Regexps (well, almost)
> 	class DictionaryMatcher
> 	  alias_method :===, :=~
> 	  alias_method :match, :=~
> 	end
>
> If you can add additional features, like a case insensitivity option when
> creating a new DictionaryMatcher this is also very useful.

What's the ruling on priority and "greediness"?  In other words,
given:

   dm << "hi"
   dm << "child"

what would:

   dm =~ "children"

give?  Would it be different if you added "child" first?  Or is there
a rule about finding the longest match?


David

-- 
                   David A. Black | dblack@wobblini.net
Author of "Ruby for Rails"   [1] | Ruby/Rails training & consultancy [3]
DABlog (DAB's Weblog)        [2] | Co-director, Ruby Central, Inc.   [4]
[1] http://www.manning.com/black | [3] http://www.rubypowerandlight.com
[2] http://dablog.rubypal.com    | [4] http://www.rubycentral.org