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

iakuf

求两个字符串的最大公共子串,是一个程序员们常常考到和想到的题目，呵呵，我用perl实现了一下,听讲是当年微软面试时要求做的一个程序,写一个返回两个任意字串中最大公共串的函数，即abcdef 和 qcfbcc 返回值为bc语言不限

sub string($$){
  my ($strmin,$strmax) = @_;
       for( my $i = 0; $i < length($strmax); $i++) {
           $lstrmin = substr($strmin, $i);
           my $nowstr;
           for(my $j=0; $j< length($lstrmin);$j++){
                 my @list=split '',$lstrmin;
                 $nowstr .= @list[$j];
                 if (index($strmax, $nowstr)>=1 && length($nowstr) > length($r)){
                        $r = $nowstr;
                }

        }
    }
        return  $r;
}

修改了自己的代码，。。。呵呵，原来写的是有点问题.现在修正，晚点测试看看谁的跑的快      




对求两个字符串这种问题，好象算法蛮多的，很需要写程序的人的水平的。。。还有另一个问题，就是要是有中文怎么办

[ 本帖最后由 iakuf 于 2009-2-2 11:53 编辑 ]

khandielas

楼主写的象Perl写的C 程序

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

my ($str1, $str2) = @ARGV;
my %hash1;
my %hash2;
@hash1{split '', $str1} = ();
foreach ( split '', $str2) {
        if (exists $hash1{$_} && ! exists $hash2{$_}) {
                print $_;
                $hash2{$_} = undef;
        }
}

ubuntu:~/programming/perl_prog$ ./extract_common_char.pl abcdefg mdeaafgnp
deafg

如果是用一个hash,会输出 a 俩次：  deaafg

iakuf

刚学习写perl，我是个菜菜

wxlfh

自己搞了个，班门弄斧，呵呵

1. sub max_mutual_str {
   
2.         my($min,$max) = @_;
   
3.         if (length($min)>length($max)) {
   
4.                 ($min,$max) = ($max,$min);
   
5.         }
   
6.         my $len = length($min);
   
7.         foreach my $rest (0..$len-1) {
   
8.                 foreach my $pos (0..$rest) {
   
9.                         my $str = substr($min,$pos,($len-$rest));
   
10.                         return $str if $max =~ /$str/;
    
11.                 }
    
12.         }
    
13.         return undef;
    
14. }
    
15. 
    
16. $str1 = '369abcdefg/789';
    
17. $str2 = '123bcdefg/0147123';
    
18. $str = max_mutual_str($str1,$str2);
    
19. print "\t$str\n";

复制代码

输出

1. bcdefg/

复制代码

iakuf

wxlfh写的这个非常不错啊。。。
khandielas写的其实是一个一个字符的。

wxlfh

最近中了正则表达式的毒，不自觉地用上了，不知道会不会有效率的问题？
见笑，见笑，呵呵。

machine

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

这个是不是有问题？

machine

#!/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;$i<$#list1+1;$i++){     for(my $j=0;$j<$#list2+1;$j++){        $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";

[ 本帖最后由 machine 于 2008-12-14 22:39 编辑 ]

wxlfh

machine，你的思路不好懂啊，还是我的直观一点，简洁一点

machine

我这个算法，用的是一个比较老套的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了。

上面的那个多少还有点像用perl写的c程序，下面给个更像perl程序的：

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