[erlang-questions] Longest prefix match

[Sean Hinde]

I found this user contribution quite inspirational when approaching  
this issue:

http://www.erlang.org/user.html#anal-1.0

Rather than store an int/bigint for intermediate results it would  
probably be enough to store the list of digits so far

Sean

On 29 Nov 2007, at 22:19, Dragan Zubac wrote:

> Hello
>
> A couple of questions regarding 'lpm' algorithm if anyone has any
> experience with this.
>
> What would be the most elegant and efficient way for LPM ? For
> example,we have some list of numbers:
>
> - 889123456
> - 44712345678
> - 5550123456789
> - 32112345
> - 5501
>
> and the desired number for example:
>
> 550123555666
>
> I guess the most efficient way would be to use some sort of 'tree' and
> traverse each number from the beginning of destination number and  
> check
> it in number's list and if we can't match N position to claim it to be
> the longest prefix match ?
>
> Second question is the same as question one,but implies that to have
> some additional data with prefix (route,price,user_id,etc.),what would
> be algorithm looks like in this situation ? For example:
>
> - 889123456,100
> - 44712345678,100
> - 5550123456789,101
> - 32112345,101
> - 5501,100
> - 5550123456789,100
>
> number is 550123555666,100 ,the problem would be to find LPM for
> specific price (100),in this case there's no unique prefix,but there's
> unique prefix+price 'object'.
>
> Anybody had any experience with this issues ?
>
> Sincerely
>
> Dragan Zubac
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions