[erlang-questions] Library proposal: O(N+M) suffix/2
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