[erlang-questions] Library proposal: O(N+M) suffix/2

Richard O'Keefe ok@REDACTED
Tue Feb 10 04:11:19 CET 2009


The lists module in Erlang's standard library
offers a function lists:suffix(Suffix, List)
which takes O(|Suffix|.|Lists|) time.
Most of this is spent inside the head testing
whether List is equal to Suffix yet; the rest
of the work is O(|List|).

It is possible to implement this function in
O(|Suffix| + |Lists|) time, and I propose that
it should be done.  Here's the code:

suffix(Suffix, List) ->
     Delta = length(List) - length(Suffix),
     ( Delta >= 0 andalso nthtail(Delta, List) =:= Suffix ).







More information about the erlang-questions mailing list