PRINT LevenshteinDistance("abc", "xyz")
PRINT LevenshteinDistance("abc", "xyzd")
PRINT LevenshteinDistance("abc", "abcdef")
PRINT LevenshteinDistance("abc", "abcd")
PRINT LevenshteinDistance("カラクリ", "ボンゴレ")
PRINT LevenshteinDistance("テスト", "テストパターン")

// https://ohnishiakira.hatenadiary.org/entry/20090809/1249845529
// をuwscに実装
function min3(a, b, c)
	result = a
	if b<a then result = b
	if c<result then result = c
fend

function max(a, b)
	result = a
	if b>a then result = b
fend

const LD_STRMAX=100
function LevenshteinDistance(s1, s2)
	DIM len1 = length(s1)+1
	DIM len2 = length(s2)+1
	DIM str1[0], str2[0]
	DIM array[LD_STRMAX+1][LD_STRMAX+1]
	result = -1;
	PRINT s1+"("+len1+") "+s2+"("+len2+")"

	if len1>LD_STRMAX or len2>LD_STRMAX then exit

	resize(str1, length(s1)-1)
	resize(str2, length(s2)-1)
	for i=0 to length(s1)-1
		str1[i] = copy(s1, i+1, 1)
	next
	for i=0 to length(s2)-1
		str2[i] = copy(s2, i+1, 1)
	next
	for i1=0 to len1-1
		array[i1][0] = i1
	next
	for i2=0 to len2-1
		array[0][i2] = i2
	next

	for i1=1 to len1-1
		for i2=1 to len2-1
			cost = 0
			if str1[i1-1] <> str2[i2-1] then cost = 1
			array[i1][i2] = min3(array[i1-1][i2]+1, array[i1][i2-1]+1, array[i1-1][i2-1]+cost)
		next
	next
	result = array[len1-1][len2-1] / max(len1-1, len2-1)
fend