%%% bm -- Boyer-Moore search
%%% Author: Steve Vinoski (http://steve.vinoski.net/), 15 October 2007.
%%%
%%% Updated 12 April 2011 to handle repeated patterns in search string.
%%%
-module(bm).
-vsn("0.2").
-author('vinoski@ieee.org').
-export([find/2]).

%% [Match_positions]
find(Str, Bin) ->
    Init = init(Str),
    find(Bin, Init, 0, []).

init(Str) ->
    Strlen = length(Str),
    Tbl = set_shifts(Str, Strlen),
    {Tbl, list_to_binary(Str), lists:reverse(Str), Strlen}.

set_shifts(Str, Len) ->
    erlang:make_tuple(256, Len, set_shifts(Str, 0, Len, [])).
set_shifts(_Str, Count, Len, Acc) when Count =:= Len-1 ->
    lists:reverse(Acc);
set_shifts([H|T], Count, Len, Acc) ->
    Shift = Len - Count - 1,
    set_shifts(T, Count+1, Len, [{H+1,Shift}|Acc]).

get_next_shift([H|T1], [H|T2], Comparisons, Tbl) ->
    get_next_shift(T1, T2, Comparisons+1, Tbl);
get_next_shift([H|_], _, Comparisons, Tbl) ->
    max(element(H+1, Tbl) - Comparisons, 1).

find(Bin, {_, _, _, Len}, Pos, Acc) when size(Bin) < (Pos + Len) ->
    lists:reverse(Acc);
find(Bin, {Tbl, BStr, RevStr, Len}=SearchCtx, Pos, Acc) ->
    case Bin of
        <<_:Pos/binary, BStr:Len/binary, _/binary>> ->
            find(Bin, SearchCtx, Pos+Len, [Pos|Acc]);
        <<_:Pos/binary, NoMatch:Len/binary, _/binary>> ->
            RevNoMatch = lists:reverse(binary_to_list(NoMatch)),
            Shift = get_next_shift(RevNoMatch, RevStr, 0, Tbl),
            find(Bin, SearchCtx, Pos+Shift, Acc)
    end.