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

surfybeach

或者可以读读cpan模块 Algorithm::Diff 的源码，函数LCS就是干这个的，求最长公共子串。

[ 本帖最后由 surfybeach 于 2009-3-12 06:39 编辑 ]

xiaojao

原帖由 wxlfh 于 2008-12-14 15:10 发表
自己搞了个，班门弄斧，呵呵
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 ...

有个不算BUG的BUG，当有两个都符合条件时，只能求出其中一个字符串，比如：
my $str1 = '123456abcd';
my $str2 = '234dddabc';
只能求出：234,而不能求出abc

李寻欢92

回复 1# iakuf

1. #!/usr/bin/perl -w
   
2. #求两字符串最大公共串
   
3. use strict;
   
4. use 5.010;
   
5. my $str_1 = "abefdh";
   
6. my $str_2 = "jfdjjabe";
   
7. my $i = 0;
   
8. my $j;
   
9. my $len_1 = rindex $str_1."\$","\$";
   
10. my @result;
    
11. my $max = 0;
    
12. while ($i<$len_1) {
    
13.     $j = $len_1-1;
    
14.     while ($j>=$i) {
    
15.         my $sub = substr($str_1,$i,$j-$i+1);
    
16.         if (index($str_2,$sub) != -1) {
    
17.             my $tmp = rindex $sub."\$","\$";
    
18.             if ($tmp > $max) {
    
19.                 pop @result;
    
20.                 push @result,$sub;
    
21.                 $max = $tmp;
    
22.                 last;
    
23.             } elsif ($tmp == $max) {
    
24.                 push @result,$sub;
    
25.                 last;
    
26.             } else {
    
27.                 1;
    
28.             }
    
29.         }
    
30.         $j--;
    
31.     }
    
32.     $i++;
    
33. }
    
34. print "@result\n";
    

复制代码

iamlimeng

开始理解错误，纠正一下。

wxlfh

有个不算BUG的BUG，当有两个都符合条件时，只能求出其中一个字符串，比如：
my $str1 = '123456abcd';
...
xiaojao 发表于 2009-03-31 17:34

    的确，我这个东西很不成熟。

iamlimeng

我开始也是有这个疑惑，若有多个公共子串，应该如何计算。我在wxlfh代码基础上改了一下，能获得长度大于2的公共子串：

1. #!/usr/bin/perl
   
2. 
   
3. sub max_mutual_str {
   
4.         my($min,$max) = @_;
   
5.         if (length($min)>length($max)) {
   
6.                 ($min,$max) = ($max,$min);
   
7.         }
   
8.         my $len = length($min);
   
9.         my $result;
   
10.          my $pos = 0;
    
11.          while ($pos < $len-1) {
    
12.                  my $rest = $len-$pos;
    
13.                   my $check = 0;
    
14.                   while ($rest > 1) {
    
15.                            my $str = substr($min,$pos,$rest);
    
16.                            print "$pos $rest $str\n";
    
17.                            if ($max =~ /$str/) {
    
18.                                     $result .= " $str";
    
19.                                     my $skip = length($str);
    
20.                                     $pos += $skip;
    
21.                                     $rest -= $skip;
    
22.                                     $check = 1;
    
23.                            }
    
24.                            else { $rest--; }
    
25.                            select(undef,undef,undef,0.05);
    
26.                   }
    
27.                   $pos++ if (!$check);
    
28.         }
    
29.         if ($result) { return($result); }
    
30.         else { return("Mutual String Not Found!"); }
    
31. }
    
32. 
    
33. my $str1 = '123456abcdefeeeee';
    
34. my $str2 = '234dddabcdegeeee';
    
35. $str = max_mutual_str($str1,$str2);
    
36. print "$str\n";

复制代码

输出：234 abcde eeee

我加了显示计算过程的代码。以上代码可能不够简洁，等高手指点。

blackold

1. #!/usr/bin/perl
   
2. use strict;
   
3. use warnings;
   
4. 
   
5. my $str1 = ...;
   
6. my $str2 = ...;
   
7. my $str = $str1 . "\n" . $str2;
   
8. 
   
9. my @substr = sort { length($b) <=> length($a) } $str =~ /(.+)(?=.*\n.*\1)/g;
   
10. my @result = grep { length == length $substr[0] } @substr;
    
11. print "@result\n";
    

复制代码

iamlimeng

回复 37# blackold


这个代码太帅了。

可能需要小改一下，输出很接近正确结果了，但还得不到完全正确的结果。

blackold

回复 38# iamlimeng


    代码不规范，结果应该是对的(假设字符串不包含\n)啊？

iamlimeng

回复 39# blackold


my $str1 = 'dddabd123456abcdefeeeee';
my $str2 = '234dddabcdegeeee';

输出：
dddab
abcde

末尾的eeee没有输出

LZ再调试一下程序。