lcs－最大公共子串算法perl版

自己用perl写的一个lcs（最大公共子串）算法的程序：

我这个算法，用的是一个比较老套的lcs算法。以前用c写过，在perl下又模仿实现了一下。

算法大概描述就是，分别用两个字符串作为横坐标和纵坐标建一个矩阵，遇到横竖字符相同的时候把这点的值设成1，否则设成零，最后矩阵中最长的不为零的对角线就是最大子字串。
例如：

	m	a	c	h	i
a	0	1	0	0	0
b	0	0	0	0	0
m	1	0	0	0	0
a	0	1	0	0	0
c	0	0	1	0	0

这样有点问题：建完矩阵还要去找最长对角线，麻烦。
解决方案是：相等时不只把矩阵元素设为“1”，而是设成它左上角的元素值加一。
例如：

	m	a	c	h	i
a	0	1	0	0	0
b	0	0	0	0	0
m	1	0	0	0	0
a	0	2	0	0	0
c	0	0	3	0	0

所以矩阵建好后，找到矩阵中最大的元素就ok了。

#!/usr/bin/perl

sub max_mutual_str {
  my($str1,$str2) = @_;
  my %cmp;
  my $max;
  my @list1=split '',$str1;
  my @list2=split '',$str2;
  for my $i (0..$#list1) {

    for my $j (0..$#list2) {

       $cmp{$i.$j}=($list1[$i] eq $list2[$j]) ? (1+$cmp{($i-1).($j-1)}) : 0;
       $max=$cmp{$i.$j} if ($cmp{$i.$j}>$max);
       print "$cmp{$i.$j}";
    }
    print "\n";
  }
  for (keys %cmp){
      if ($cmp{$_} == $max ){
         my $offset=substr($_,0,1)+1-$max;
         return substr($str1,$offset,$max);
      }
  }
}

my ($str1,$str2) = @ARGV;
my $str= max_mutual_str($str1,$str2);
print "$str\n";


后来发现，既然都找到最大的公共字符串了，干嘛还要在遍历一遍散列呢，真的够傻的，惭愧啊：

 

#!perl


sub max_mutual_str {
  my($str1,$str2) = @_;
  my %cmp;
  my $max;
  my $beginning_station; #beginning station of the common string in $str1

  my @list1=split '',$str1;
  my @list2=split '',$str2;
  for my $i (0..$#list1){
    for my $j (0..$#list2){
  $cmp{$i.$j}=($list1[$i] eq $list2[$j]) ? (1+$cmp{($i-1).($j-1)}) : 0;
        if ($cmp{$i.$j}>$max){
           $max=$cmp{$i.$j};
           $beginning_station=$i+1-$max;
         }
       print "$cmp{$i.$j}";
    }
    print "\n";
  }

  return substr($str1,$beginning_station,$max);

}

my ($str1,$str2) = @ARGV;
my $str= max_mutual_str($str1,$str2);
print "$str\n";