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

minority

machine 发表于 2008-12-15 09:01
我这个算法，用的是一个比较老套的lcs算法。以前用c写过，在perl下又模仿实现了一下。

算法大概描述就 ...

算法不错！！！！

mcshell

回复 59# gongyonghui2


    我也来试试看

1. #!/usr/bin/perl
   
2. use strict;
   
3. use warnings;
   
4. use Data::Dumper;
   
5. my %hash1;
   
6. my %hash2;
   
7. my @arr;
   
8. my $str1 = 'aab12345678';
   
9. my $str2 = 'ab1234yb1234567';
   
10. $str1 =~ /(.*?)(?{$hash1{$1}=$1})(*F)/;
    
11. $str2 =~ /(.*?)(?{$hash2{$1}=$1})(*F)/;
    
12.    for (keys %hash1){
    
13.        my  $k = $_;
    
14.         push  @arr,$k if exists $hash2{$k};   
    
15.    }
    
16.    my($max,$min)=sort{length($b) cmp length($a)}@arr;
    
17.    for (@arr){
    
18.     if(length($_)==length($max)){
    
19.         print "$_\n";
    
20.     }
    
21.    }
    
22. output:
    
23. b1234567
    

复制代码

blackold

回复 59# gongyonghui2


    多谢指正!

    确实如你所说，原来的代码是错误的。try：

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

复制代码

blackold

回复 62# mcshell


    学习！

mcshell

回复 64# blackold


    黑哥太谦虚了   多向黑哥请教才是

hzy2hzy

machine 发表于 2008-12-15 09:01
我这个算法，用的是一个比较老套的lcs算法。以前用c写过，在perl下又模仿实现了一下。

算法大概描述就 ...

赞算法！

gongyonghui2

回复 63# blackold

不会用回溯控制，改了一下你的代码，这种方式也行：
#!/usr/bin/perl
use strict;
use warnings;

my $str1 ="aab12345678";
my $str2 = "ab1234yb1234567";
my $str = $str1 . "\n" . $str2;

my @substr=sort { length($b) <=> length($a) } map {substr($str,$_)=~/^(.+)(?=.*\n.*\1)/} 0..length($str1)-1;
my @result = grep { length == length $substr[0] } @substr;
print "@result\n";

blackold

回复 67# gongyonghui2


  好!
学习!

qinyudd

1. #!/usr/bin/perl
   
2. open STR1, '/opt/str1.txt';
   
3. open STR2, '/opt/str2.txt';
   
4. our $min;
   
5. our $max;
   
6. our $sum;
   
7. $str1 = <STR1>;
   
8. $str2 = <STR2>;
   
9. $len   = length($str1);
   
10. $max   = $len;
    
11. $min   = 0;
    
12. $point = int( $max / 2 );
    
13. &match($point);
    
14. sub match {
    
15.     my ($point) = @_;
    
16.     $end = $len - $point;
    
17.     for $begin ( 0 .. $end ) {
    
18.         $lcs= substr( $str1, $begin, $point );
    
19.         if ( $str2 =~ /$lcs/ ) {
    
20.             $aver = $max - $min;
    
21.             if ( $aver <= 1 ) {
    
22.                 print $lcs;
    
23.                 exit;
    
24.             }
    
25.             else {
    
26.                 $min = $point;
    
27.                 $point = $min + int( ( $max - $min ) / 2 );
    
28.                 &match($point);
    
29.             }
    
30.         }
    
31.     }
    
32.     $max = $point;
    
33.     $point = $max - int( ( $max - $min + 1 ) / 2 );
    
34.     &match($point);
    
35. 
    
36. }

复制代码

二分法
如果公共子串较长有奇效

anders0913

machine 发表于 2008-12-15 09:01
我这个算法，用的是一个比较老套的lcs算法。以前用c写过，在perl下又模仿实现了一下。

算法大概描述就 ...

学习了