--!native
--!optimize 2
-- Compiled with roblox-ts v3.0.0
local TS = _G[script]
local CharAt = TS.import(script, script.Parent.Parent, "Utils", "CharAt")
local function LargeStringsDamerauLevenshteinDistanceScore(term, query)
	local m = #term
	local n = #query
	if m == 0 then
		return n
	end
	if n == 0 then
		return m
	end
	local _exp = table.create(n + 1, 0)
	-- ▼ ReadonlyArray.map ▼
	local _newValue = table.create(#_exp)
	local _callback = function(_, i)
		return i
	end
	for _k, _v in _exp do
		_newValue[_k] = _callback(_v, _k - 1, _exp)
	end
	-- ▲ ReadonlyArray.map ▲
	local prev_row = _newValue
	local curr_row = table.create(n + 1, 0)
	local pre_previous_row = table.create(n + 1, 0)
	do
		local i = 1
		local _shouldIncrement = false
		while true do
			if _shouldIncrement then
				i += 1
			else
				_shouldIncrement = true
			end
			if not (i <= m) then
				break
			end
			curr_row[1] = i
			do
				local j = 1
				local _shouldIncrement_1 = false
				while true do
					if _shouldIncrement_1 then
						j += 1
					else
						_shouldIncrement_1 = true
					end
					if not (j <= n) then
						break
					end
					local cost = if CharAt(term, i - 1) == CharAt(query, j - 1) then 0 else 1
					curr_row[j + 1] = math.min(prev_row[j + 1] + 1, curr_row[j] + 1, prev_row[j] + cost)
					-- Transposition check
					if i > 1 and j > 1 and CharAt(term, i - 1) == CharAt(query, j - 2) and CharAt(term, i - 2) == CharAt(query, j - 1) then
						curr_row[j + 1] = math.min(curr_row[j + 1], pre_previous_row[j - 1] + 1)
					end
				end
			end
			pre_previous_row, prev_row, curr_row = prev_row, curr_row, pre_previous_row
		end
	end
	return prev_row[n + 1]
end
return {
	LargeStringsDamerauLevenshteinDistanceScore = LargeStringsDamerauLevenshteinDistanceScore,
}