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

sub max_mutual_str {

	my($min,$max) = @_;

	if (length($min)>length($max)) {

		($min,$max) = ($max,$min);

	}

	my $len = length($min);

	foreach my $rest (0..$len-1) {

		foreach my $pos (0..$rest) {

			my $str = substr($min,$pos,($len-$rest));

			return $str if $max =~ /$str/;

		}

	}

	return undef;

}



$str1 = '369abcdefg/789';

$str2 = '123bcdefg/0147123';

$str = max_mutual_str($str1,$str2);

print "\t$str\n";

bcdefg/

原帖由 khandielas 于 2008-12-14 06:33 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9784912&ptid=1333575]
楼主写的象Perl写的C 程序

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

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

原帖由 khandielas 于 2008-12-14 06:33 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9784912&ptid=1333575]
楼主写的象Perl写的C 程序

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

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

原帖由 machine 于 2008-12-15 09:01 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9787939&ptid=1333575]

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

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

原帖由 machine 于 2008-12-15 09:01 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9787939&ptid=1333575]

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

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

原帖由 machine 于 2008-12-15 09:01 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9787939&ptid=1333575]

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

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

原帖由 adminsinx 于 2008-12-15 11:05 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9788839&ptid=1333575]



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

原帖由 machine 于 2008-12-15 09:01 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9787939&ptid=1333575]

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

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

#!/usr/bin/perl



&max_index_of_two_string('xabcdxxxveafa', 'eabcafeveafaeagagade');



sub max_index_of_two_string()

{

    my ($str1, $str2) = @_;

    my $max_index_of_two_string = undef;

    if (length($str1) < length($str2)) { 

        my $str = $str1;

        $str1 = $str2;

        $str2 = $str;

    }

    my $mark = 2;

    while (length($str2) > 0) {

        while ($mark <= length($str2)) {

            my $pattern = substr($str2, 0, $mark);

            if ($str1 =~ /$pattern/) { 

                if (length($pattern) > length($max_index_of_two_string)) {

                    $max_index_of_two_string = $pattern;

                }

            }

            $mark++;

        }

        if ($str2 =~ /(.)(.*)/) {

            $str2 = $2;

            $mark = 2;

        }

    }

    print $max_index_of_two_string;

}

原帖由 machine 于 2009-1-6 10:36 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9903046&ptid=1333575]
my $str = $str1;
        $str1 = $str2;
        $str2 = $str;
标准c语言写法。
perl 写法：
($str1,$str2)=($str2,$str1); 

原帖由 iakuf 于 2008-12-14 00:37 发表 [url=http://bbs3.chinaunix.net/redirect.php?goto=findpost&pid=9784818&ptid=1333575]
回复1楼的:
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;
}

原帖由 wxlfh 于 2008-12-14 15:10 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=9785738&ptid=1333575]
自己搞了个，班门弄斧，呵呵
sub max_mutual_str {
        my($min,$max) = @_;
        if (length($min)>length($max)) {
                ($min,$max) = ($max,$min);
        }
        my $len = length($min);
        foreach my $rest (0..$len-1 ...