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

rubyish

不得不赞一个。
那个效率更高？ 高手能否帮分析一下。

blackfur

#!d:/perl64/bin/perl
use strict;
use warnings;

#match max string
sub m_m_s{
        my $max='';
        #string1's position,string2's position
        my $p1=0;
        my $p2=0;
        #length of s2
        my $l2;
        my ($s1,$s2)=split(',',$_);
        if($s1&&$s2){
                $l2=length($s2);
                my $l1=length($s1);
                if ($l1>$l2) {
                ($s1,$s2) = ($s2,$s1);
                                ($l1,$l2) = ($l2,$l1);
        }
foreach my $j (0..($l1-1)) {
                foreach $p2 (0..($l2-1)) {
                        while (substr($s1,$p1,1) eq substr($s2,$p2,1)) {
                                if ($p1 eq ($l1-1)) {
                                        $p1+=1;
                                        last;
                                }
                                $p1++;$p2++;
                        }
                        unless($p1 eq $j){
                                        if (length($max)<($p1-$j)) {
                                                $max=substr($s1,$j,$p1-$j);
                                        }
                        }
                                $p1=$j;
                }
}
                        if ($max eq '') {
                $max.='no match!';
                        }
        }else {
                print "please input two string separated with comma!"
        }
        return $max;
}
        print 'hello> ';
while (<stdin>) {
        chomp $_;
        #enter q or Q to quit!
        if (/[qQ]/) {
                exit 0;
        }
        print m_m_s($_),"\nhello> ";
}
很菜，别见笑

xo1980

xo1980

zzwevil

应该是很笨的方法吧，但是也想了好久，不知道效果如何，有人愿意帮忙测试吗？
#!/usr/bin/perl
$a="aaabdddddddddbbbbbbbcddddccc";
$b="adbbbbbbbddddddddddbbbdcccdddd";
$c1=0;
$c2=0;
$op1="";
$op2="";
$lena = length($a);
$lenb = length($b);
for($i=1;$i<=$lena;$i++)
{
for($j=0;$j<=$lena;$j++)
{
       $fuck=substr($a,$j,$i);
                $d = ($b =~ /$fuck/);
       if($d){
       $op1=$fuck;
                $c1= length($op1);
                }
                if($c1>=$c2){
       $c2=$c1;
       $op2=$op1;
       }
        }
}
print "$c2 $op2";

方兆国儿

@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";

复制代码

向大神学习

gdw1986

回复 4# wxlfh

请问你这种算法不存在遗漏吗，你的应该都是比如取abcd不行的话就到abc每次都是从前面取的吧，存不存在这种比如刚好和bcd匹配的情况被遗漏呢，菜鸟问的
   

a448677947

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;
}

这个方法好！！！
my $str = substr($min,$pos,($len-$rest));
是“substr EXPR, OFFSET, LEN”，从min的最长字符串一次，字符串减一，则两次，一直循环，一匹配则退出，但是如果有两个相同的，匹配，则只显示前面一个。
例如：
$min = 'a1b2';
$max = 'a13db2';

则脚本只会取出“a1”，会忽略“b2”,

david_95

琢磨半天，我也写了一个，呵呵

sub findMaxMatch1{
         my ($str1,$str2)=@_;
         my ($long,$short)=(length($str1)>length($str2))?($str1,$str2)$str2,$str1);
         my $len=length($short);
         my $width;
         for(my $width=$len;$width>1;$width--){
                 foreach my $pos(0..$len-1){
                         if(($pos+$width) > $len) {next;}
                         my $tmp=substr($short,$pos,$width);
                         return $tmp if($long=~/$tmp/g);
                 }
         }
}