Skip to content

Instantly share code, notes, and snippets.

@SwadicalRag
Created December 24, 2022 05:41
Show Gist options
  • Save SwadicalRag/6bb2309633b60908b96bb5f6e1027164 to your computer and use it in GitHub Desktop.
Save SwadicalRag/6bb2309633b60908b96bb5f6e1027164 to your computer and use it in GitHub Desktop.
Fuzzy substring match in lua
function fuzzySubstringMatch(str,match,maxDiscrepancies)
local minIdx
local minDiscrepancies = 1 / 0
for idx=1,#str do
local curIdx = idx
local discrepancies = 0
local matchIdx = 1
while matchIdx <= #match do
local srcChar,srcCharNext = str:byte(curIdx + matchIdx - 1,curIdx + matchIdx)
local matchChar,matchCharNext = match:byte(matchIdx,matchIdx + 1)
if srcChar ~= matchChar then
discrepancies = discrepancies + 1
if matchChar == srcCharNext then
-- addition
curIdx = curIdx + 1
elseif matchCharNext == srcChar then
-- deletion
curIdx = curIdx - 1
else
-- all other cases treat as substitution
end
end
if discrepancies > maxDiscrepancies then break end
matchIdx = matchIdx + 1
end
if discrepancies <= maxDiscrepancies then
minDiscrepancies = math.min(minDiscrepancies,discrepancies)
if minDiscrepancies == discrepancies then
minIdx = idx
end
end
end
return minDiscrepancies,minIdx
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment