Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
-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)).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment