Готовая программа

#!/usr/bin/perl

use warnings;

sub levenshtein
{
	my ($a, $b)=@_;
	if(length($a) and length($b))
	{
		if(substr($a, 0, 1) eq substr($b, 0, 1))
		{
			return levenshtein(substr($a, 1), substr($b, 1));
		}
		else
		{
			my $da=levenshtein(substr($a, 1), $b);
			my $db=levenshtein($a, substr($b, 1));
			return 1+($da<$db? $da: $db);
		}
	}
	else
	{
		return length($a)||length($b);
	}
}

my ($a, $b)=@ARGV;
utf8::decode($_) for $a, $b;
print 1-levenshtein($a, $b)/(length($a)+length($b)), "\n";
#!/usr/bin/perl

use warnings;

sub levenshtein
{
	my ($a, $b)=@_;
	my $la=length $a;
	my $lb=length $b;

	my @agenda=([0, 0, 0]);
	my $result=INFINITY;

	while(@agenda)
	{
		my ($i, $j, $cost)=@{pop @agenda};
		if($i==$la or $j==$lb)
		{
			$result=$cost+$la+$lb-$i-$j
				if $cost+$la+$lb-$i-$j<$result;
			next;
		}
		if(substr($a, $i, 1) eq substr($b, $j, 1))
		{
			push @agenda, [$i+1, $j+1, $cost];
		}
		else
		{
			push @agenda, [$i+1, $j, $cost+1], [$i, $j+1, $cost+1];
		}
	}
	return $result;
}

my ($a, $b)=@ARGV;
utf8::decode($_) for $a, $b;
print 1-levenshtein($a, $b)/(length($a)+length($b)), "\n";
#!/usr/bin/perl

use warnings;

sub levenshtein
{
	my ($a, $b)=@_;

	my @bellman;
	my $la=length $a;
	my $lb=length $b;

	$bellman[$_][0]=$_ for 0..$la;
	$bellman[0][$_]=$_ for 0..$lb;

	for my $j(1..$lb)
	{
		for my $i(1..$la)
		{
			$bellman[$i][$j]=$bellman[$i-1][$j]+1;
			$bellman[$i][$j]=$bellman[$i][$j-1]+1
				if $bellman[$i][$j]>$bellman[$i][$j-1]+1;

			if(substr($a, $i-1, 1) eq substr($b, $j-1, 1))
			{
				$bellman[$i][$j]=$bellman[$i-1][$j-1]
					if $bellman[$i][$j]>$bellman[$i-1][$j-1];
			}
		}
	}
	return $bellman[$la][$lb];
}

my ($a, $b)=@ARGV;
utf8::decode($_) for $a, $b;
print 1-levenshtein($a, $b)/(length($a)+length($b)), "\n";
Информатика-54© А. Н. Швец