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

adminsinx

UID: 18793
帖子: 56
积分: 128
在线时间: 4 小时

11^# adminsinx 发表于 2008-12-15 11:05

QUOTE:

原帖由 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

UID: 22014
帖子: 1
积分: 2
在线时间: 10 分钟

12^# wxlfh 发表于 2008-12-15 18:36

QUOTE:

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

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

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

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

churchmice

UID: 31829
帖子: 2
积分: 4
在线时间: 10 分钟

13^# churchmice 发表于 2008-12-15 19:31

QUOTE:

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

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

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

仰慕阿

machine

UID: 43012
帖子: 185
积分: 425
在线时间: 1 天 22 小时

14^# machine 发表于 2008-12-16 10:43

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

smonkey0

UID: 42438
帖子: 74
积分: 170
在线时间: 7 小时

15^# smonkey0 发表于 2008-12-16 13:24

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

machine

UID: 43012
帖子: 185
积分: 425
在线时间: 1 天 22 小时

16^# machine 发表于 2008-12-17 10:47

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

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

UID: 22959
帖子: 5
积分: 11
在线时间: 10 分钟

17^# DQP 发表于 2008-12-17 14:26

QUOTE:

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

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

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

不得不赞一个

MMMIX

UID: 31964
帖子: 137
积分: 315
在线时间: 1 天 1 小时

18^# MMMIX 发表于 2008-12-17 14:36

QUOTE:

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

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

见 perldata 中的 Slices

iakuf

UID: 45144
帖子: 114
积分: 262
在线时间: 18 小时

19^# iakuf 发表于 2008-12-19 21:44

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

UID: 14900
帖子: 4
积分: 9
在线时间: 10 分钟

20^# lzs45 发表于 2008-12-19 22:25

QUOTE:

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

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

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

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