Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

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.

Replies are listed 'Best 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?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1027476]
[Corion]: Discipulus: Nah, I'm thinking of posting more short stuff, but not all of it is fit for, more something a bit longer than Twitter but shorter than my usual b.p.o module posts
[Corion]: But Google+ is tedious and I'd like to keep my posts on an open platform instead, which can be followed via RSS

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2017-05-26 07:42 GMT
Find Nodes?
    Voting Booth?