Re: 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
[download]

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 'Best First'.
Re^2: Longest String Matching by hdb (Monsignor) 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...	[reply]
Re^3: Longest String Matching by space_monk (Chaplain) on Apr 08, 2013 at 12:08 UTC
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.	[reply]
Re^4: Longest String Matching by hdb (Monsignor) on Apr 08, 2013 at 12:17 UTC
Adding the empty string to the lexikon allows the following shortening: `$lookup{''} = 1; substr($word, 0, 1) = "" while !exists $lookup{$word};` [download]	[reply] [d/l]