> Wow. My solution's a real slowpoke compared to yours, even thought 
> mine's
> asymptotically faster: O(string.length) versus
> O(string.length* max(keys.length))
> 
> I wonder what's slowing mine down so much, since these are in many ways
> the same.

Well, do we get the same results from the scan of the big file? Recall 
that in the scan I skip over strings once I see they are in the 
dictionary, which cuts out a lot of work and may yield far fewer 
results.

For example, if the text to be scanned is

abacusqwertyark

and the dictionary contains the words abacus and ark, the index into the 
string will move as follows:

abacusqwertyark # Begin
^

abacusqwertyark # Found abacus, skip it
      ^
abacusqwertyark # Found ark
               ^

A solution that did not skip the words would find additional substrings, 
for example:

abacusqwertyark # Begin
^

abacusqwertyark # Found abacus, start again on next character
 ^
... omit some steps ...

abacusqwertyark # Found "us"
    ^

Maybe I'm cheating or there's some other bug in my code that omits 
results that you find :)


-- 
Posted via http://www.ruby-forum.com/.