http://en.wikipedia.org/wiki/Levenshtein_distance

levenshtein_distance.adb

function Levenshtein_Distance (Left, Right : String) return Natural is
	D : array (Left'First - 1 .. Left'Last, Right'First - 1 .. Right'Last) of Integer;
begin
	for I1 in D'Range (1) loop
		D (I1, D'First (2)) := I1;
	end loop;
	for I2 in D'Range (2) loop
		D (D'First (1), I2) := I2;
	end loop;
	for I1 in Left'Range loop
		for I2 in Right'Range loop
			declare
				Cost : Integer;
			begin
				if Left (I1) = Right (I2) then
					Cost := 0;
				else
					Cost := 1;
				end if;
				D (I1, I2) := Integer'Min (Integer'Min (
					D (I1 - 1, I2) + 1, -- insert
					D (I1, I2 - 1) + 1), -- delete
					D (I1 - 1, I2 - 1) + Cost);
			end;
		end loop;
	end loop;
	return D (Left'Last, Right'Last);
end Levenshtein_Distance;

levenshtein_distance.ads

function Levenshtein_Distance (Left, Right : String) return Natural;
pragma Pure (Levenshtein_Distance);