12345678910111213141516171819202122232425262728293031323334353637383940 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # License: GPLv3
- # Date: 12 December 2016
- # https://github.com/trizen
- # Levenshtein distance (recursive implementation).
- # See also:
- # https://en.wikipedia.org/wiki/Levenshtein_distance
- use 5.010;
- use strict;
- use warnings;
- use List::Util qw(min);
- use Memoize qw(memoize);
- memoize('leven');
- sub leven {
- my ($s, $t) = @_;
- return length($t) if $s eq '';
- return length($s) if $t eq '';
- my ($s1, $t1) = (substr($s, 1), substr($t, 1));
- (substr($s, 0, 1) eq substr($t, 0, 1))
- ? leven($s1, $t1)
- : min(
- leven($s1, $t1),
- leven($s, $t1),
- leven($s1, $t ),
- ) + 1;
- }
- say leven('rosettacode', 'raisethysword');
|