Beefy Boxes and Bandwidth Generously Provided by pair Networks Cowboy Neal with Hat
Syntactic Confectionery Delight
 
PerlMonks  

Re: Longest String Matching

by space_monk (Chaplain)
on Apr 08, 2013 at 11:56 UTC ( #1027476=note: print w/ replies, xml ) Need Help??


in reply to Longest String Matching

I'm open to better ideas.... :-)

while (length($word) && !exists $lookup{$word}) { substr($word, 0, 1) = ""; # remove 1st char } # $word will be empty or the matched string

Update: This probably works well if the lexicon contains a lot of words as the execution time of this is proportional only to the length of the word. hdb has contributed an improvement to reduced the complexity a little, using the common trick of guaranteeing a match for zero length. There is a regex solution below this which is interesting too...

A Monk aims to give answers to those who have none, and to learn from those who know more.


Comment on Re: Longest String Matching
Download Code
Re^2: Longest String Matching
by hdb (Parson) on Apr 08, 2013 at 12:02 UTC

    I do not think it can get much better. My proposal is not very useful for large dictionaries...

      Thanks; Maybe my solution is better than I first thought! :-)
      A Monk aims to give answers to those who have none, and to learn from those who know more.

        Adding the empty string to the lexikon allows the following shortening:

        $lookup{''} = 1; substr($word, 0, 1) = "" while !exists $lookup{$word};

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1027476]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (10)
As of 2014-04-16 23:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (436 votes), past polls