shiftand.erl

-module(shiftand).

%% shiftand:match("announce", "annual_announce").

-export([match/2]).

match(Pattern, Text) ->
    PatLen = length(Pattern),
    BitMaskTable = init_table(Pattern),
    MatchMask = 1 bsl (PatLen - 1),
    InitialIndex = 0,
    D = 0,
    Index = match(false, InitialIndex, Text, D, MatchMask, BitMaskTable),
    case Index of
        -1    -> nomatch;
        Index -> Index - PatLen + 1
    end.

match(false, _Index, [], _D, _MatchMask, _BitMaskTable) ->
    -1;
match(true, Index, _Text, _D, _MatchMask, _BitMaskTable) ->
    Index-1;
match(_Matched, Index, [Char|TextRest], D, MatchMask, BitMaskTable) ->
    D2 = ((D bsl 1) bor 1) band maps:get(Char, BitMaskTable, 0),
    Matched2 = (D2 band MatchMask),
    match(Matched2 =/= 0, Index+1, TextRest, D2, MatchMask, BitMaskTable).

init_table(Pattern) ->
    init_table(Pattern, 0, maps:new()).

init_table([], _Index, Table) ->
    Table;
init_table([Char|Rest], Index, Table) ->
    Val = maps:get(Char, Table, 0),
    Val2 = Val bor (1 bsl Index),
    init_table(Rest, Index+1, maps:put(Char, Val2, Table)).