Beefy Boxes and Bandwidth Generously Provided by pair Networks
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
Replies are listed 'Oldest First'.
Re^2: Longest String Matching
by hdb (Prior) 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 examining the Monastery: (15)
As of 2015-07-07 16:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (91 votes), past polls