微软面世试题-最大公共串-求两个字符串的最大公共子串的一个有意思的题目

adminsinx

原帖由 khandielas 于 2008-12-14 06:33 发表
楼主写的象Perl写的C 程序

在Perl用hash作这些活比较典型了，

my ($str1, $str2) = @ARGV;
my %hash1;
my %hash2;
@hash1{split '', $str1} = ();
foreach ( split '', $str2) {
        if (exists $hash ...

请教@hash1{split '', $str1} = ();
这句话是什么意思？

wxlfh

原帖由 machine 于 2008-12-15 09:01 发表

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

算法大概描述就是，分别用两个字符串作为横坐标和纵坐标建一个矩阵，遇到横竖字符相同的时候把这点的值设成1，否则设 ...

你这个算法可能是C语言优化的，用C语言可能效率很高。

churchmice

原帖由 machine 于 2008-12-15 09:01 发表

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

算法大概描述就是，分别用两个字符串作为横坐标和纵坐标建一个矩阵，遇到横竖字符相同的时候把这点的值设成1，否则设 ...

仰慕阿

machine

是的，这个算法我用c语言写过，效率确实不错，就是字符串大的时候建立矩阵比较占内存，还有自己清理（perl就好多了，自动清理）。现在就是不知道用perl实现起来是不是也很高效， 比 wxlfh 那个正则的算法比较那个效率更高？ 高手能否帮分析一下。

smonkey0

有空看看生物的 blast算法。。

machine

今天早上看自己的博客，又看到这个代码，突然发现，当初竟然犯傻了，既然都找到最大的公共字符串了，干嘛还要在遍历一遍散列呢，真的够傻的，惭愧啊。

#!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";

DQP

原帖由 machine 于 2008-12-15 09:01 发表

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

算法大概描述就是，分别用两个字符串作为横坐标和纵坐标建一个矩阵，遇到横竖字符相同的时候把这点的值设成1，否则设 ...

不得不赞一个

MMMIX

原帖由 adminsinx 于 2008-12-15 11:05 发表



请教@hash1{split '', $str1} = ();
这句话是什么意思？

见 perldata 中的 Slices

iakuf

sub string($$){
   ($strmin,$strmax) = @_;
       for( my $i = 0; $i < length($strmax); $i++) {
           $lstrmin = substr($strmin, $i);
           for(my $j=0; $j< length($lstrmin);$j++){
                chop($lstrmin);
                if (index($strmax, $lstrmin)>=1 && length($lstrmin) > length($r)){
                        $r = $lstrmin;
                }

            }
    }
        return  $r;
}


第4次改进

lzs45

原帖由 machine 于 2008-12-15 09:01 发表

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

算法大概描述就是，分别用两个字符串作为横坐标和纵坐标建一个矩阵，遇到横竖字符相同的时候把这点的值设成1，否则设 ...

呵呵，学习，还是第一次见这个算法