Chinaunix

标题: 微软面世试题-最大公共串-求两个字符串的最大公共子串的一个有意思的题目 [打印本页]
作者: iakuf    时间: 2008-12-14 00:37
标题: 微软面世试题-最大公共串-求两个字符串的最大公共子串的一个有意思的题目
求两个字符串的最大公共子串,是一个程序员们常常考到和想到的题目，呵呵，我用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    时间: 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 $hash1{$_} && ! exists $hash2{$_}) {
                print $_;
                $hash2{$_} = undef;
        }
}

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

如果是用一个hash,会输出 a 俩次：  deaafg
作者: iakuf    时间: 2008-12-14 10:16
标题: 回复 #2 khandielas 的帖子
刚学习写perl，我是个菜菜
作者: wxlfh    时间: 2008-12-14 15:10
自己搞了个，班门弄斧，呵呵
  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. }

  16. $str1 = '369abcdefg/789';
  17. $str2 = '123bcdefg/0147123';
  18. $str = max_mutual_str($str1,$str2);
  19. print "\t$str\n";
复制代码

输出
  1. bcdefg/
复制代码
作者: iakuf    时间: 2008-12-14 15:52
wxlfh写的这个非常不错啊。。。
khandielas写的其实是一个一个字符的。
作者: wxlfh    时间: 2008-12-14 15:55
最近中了正则表达式的毒，不自觉地用上了，不知道会不会有效率的问题？
见笑，见笑，呵呵。
作者: machine    时间: 2008-12-14 16:18
原帖由 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    时间: 2008-12-14 22:38
#!/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    时间: 2008-12-14 23:15
machine，你的思路不好懂啊，还是我的直观一点，简洁一点
作者: machine    时间: 2008-12-15 09:01

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

算法大概描述就是，分别用两个字符串作为横坐标和纵坐标建一个矩阵，遇到横竖字符相同的时候把这点的值设成1，否则设成零，最后矩阵中最长的不为零的对角线就是最大子字串。
例如：
m ac h i
a 0 1 0 0 0
b 0 0 0 00
m 1 0 0 0 0
a 0 1 0 0 0
c 0 0 1 0 0



这样有点问题：建完矩阵还要去找最长对角线，麻烦。
解决方案是：相等时不只把矩阵元素设为“1”，而是设成它左上角的元素值加一。
例如：
m ac h i
a 0 1 0 0 0
b 0 0 0 00
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";
作者: adminsinx    时间: 2008-12-15 11:05
原帖由 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 ...



请教@hash1{split '', $str1} = ();
这句话是什么意思？
作者: wxlfh    时间: 2008-12-15 18:36
原帖由 machine 于 2008-12-15 09:01 发表

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

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

你这个算法可能是C语言优化的，用C语言可能效率很高。
作者: churchmice    时间: 2008-12-15 19:31
原帖由 machine 于 2008-12-15 09:01 发表

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

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

仰慕阿
作者: machine    时间: 2008-12-16 10:43
是的，这个算法我用c语言写过，效率确实不错，就是字符串大的时候建立矩阵比较占内存，还有自己清理（perl就好多了，自动清理）。现在就是不知道用perl实现起来是不是也很高效， 比 wxlfh 那个正则的算法比较那个效率更高？ 高手能否帮分析一下。
作者: smonkey0    时间: 2008-12-16 13:24
有空看看生物的 blast算法。。
作者: machine    时间: 2008-12-17 10:47
今天早上看自己的博客，又看到这个代码，突然发现，当初竟然犯傻了，既然都找到最大的公共字符串了，干嘛还要在遍历一遍散列呢，真的够傻的，惭愧啊。

#!perl


sub max_mutual_str {
  my($str1,$str2) = @_;
  my %cmp;
  my $max;
  my $beginning_station; #beginning station of the common string in $str1

  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;
        if ($cmp{$i.$j}>$max){
           $max=$cmp{$i.$j};
           $beginning_station=$i+1-$max;
         }
       print "$cmp{$i.$j}";
    }
    print "\n";
  }

  return substr($str1,$beginning_station,$max);

}

my ($str1,$str2) = @ARGV;
my $str= max_mutual_str($str1,$str2);
print "$str\n";
作者: DQP    时间: 2008-12-17 14:26
原帖由 machine 于 2008-12-15 09:01 发表

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

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


不得不赞一个
作者: MMMIX    时间: 2008-12-17 14:36
原帖由 adminsinx 于 2008-12-15 11:05 发表



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

见 perldata 中的 Slices
作者: iakuf    时间: 2008-12-19 21:44
sub string($$){
   ($strmin,$strmax) = @_;
       for( my $i = 0; $i < length($strmax); $i++) {
           $lstrmin = substr($strmin, $i);
           for(my $j=0; $j< length($lstrmin);$j++){
                chop($lstrmin);
                if (index($strmax, $lstrmin)>=1 && length($lstrmin) > length($r)){
                        $r = $lstrmin;
                }

            }
    }
        return  $r;
}


第4次改进
作者: lzs45    时间: 2008-12-19 22:25
原帖由 machine 于 2008-12-15 09:01 发表

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

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


呵呵，学习，还是第一次见这个算法
作者: bandaotidejia    时间: 2008-12-26 13:53
微软还用perl？

面试 面世
作者: iakuf    时间: 2008-12-26 21:21
人家当时的要求是，无论你用什么方法来写
作者: mfzz1134    时间: 2008-12-27 01:13
经典DP,开矩阵是对地,效率最高.
作者: wxlfh    时间: 2008-12-28 10:30
Perl中可能效率不是最高也说不定。
作者: cheveu    时间: 2009-01-02 13:36
我是外行，不会编程。
不过，不知道“卷积”可行不？
作者: junonly    时间: 2009-01-05 22:48
perl 新手, 写个试试

  2. #!/usr/bin/perl

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

  6. sub max_index_of_two_string()
  7. {
  8.     my ($str1, $str2) = @_;
  9.     my $max_index_of_two_string = undef;
  10.     if (length($str1) < length($str2)) {
  11.         my $str = $str1;
  12.         $str1 = $str2;
  13.         $str2 = $str;
  14.     }
  15.     my $mark = 2;
  16.     while (length($str2) > 0) {
  17.         while ($mark <= length($str2)) {
  18.             my $pattern = substr($str2, 0, $mark);
  19.             if ($str1 =~ /$pattern/) {
  20.                 if (length($pattern) > length($max_index_of_two_string)) {
  21.                     $max_index_of_two_string = $pattern;
  22.                 }
  23.             }
  24.             $mark++;
  25.         }
  26.         if ($str2 =~ /(.)(.*)/) {
  27.             $str2 = $2;
  28.             $mark = 2;
  29.         }
  30.     }
  31.     print $max_index_of_two_string;
  32. }
复制代码
作者: machine    时间: 2009-01-06 10:36
my $str = $str1;
        $str1 = $str2;
        $str2 = $str;
标准c语言写法。
perl 写法：
($str1,$str2)=($str2,$str1);
作者: junonly    时间: 2009-01-06 12:06
原帖由 machine 于 2009-1-6 10:36 发表
my $str = $str1;
        $str1 = $str2;
        $str2 = $str;
标准c语言写法。
perl 写法：
($str1,$str2)=($str2,$str1);

这样就可以swap了，又学到新东西啊。
作者: grubbyoo    时间: 2009-03-11 16:49
俺用 sql 写一个  oracle10g

select  max( replace ( sys_connect_by_path(a.t, '.'),'.') ) keep (dense_rank first order by level desc  )
   from (select rownum n, substr('abcdefg1234<*>', rownum, 1) t
           from dual
         connect by rownum <= length('abcdefg1234<*>')) a,
        
        (select rownum m, substr('12345defg1237123', rownum, 1) t
           from dual
         connect by rownum <= length('12345defg1237123')) b
  where a.t = b.t
connect by a.n = prior a.n + 1
        and b.m = prior b.m + 1
作者: dream3401    时间: 2009-03-11 21:43
原帖由 iakuf 于 2008-12-14 00:37 发表
回复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;
}


这个算法是从少到多的找,最好是从多到少的找,最长的即为最匹配的,你楼下的用正则的就是从最长开始找起,找到即是最长的.
所以我改了一下你的程序
sub mystring{
  my ($lstrmin,$r)=("","");
  my ($strmin,$strmax) = @_;
       for( my $i = 0; $i <length($strmin); $i++) {
           $lstrmin =substr($strmin,$i);
           my $nowstr;
           for(my $j=length($lstrmin); $j>length($r);$j--){
                 $nowstr =substr($lstrmin,0,$j);
                # print $nowstr;
                 if (index($strmax, $nowstr)>=1 && length($nowstr) > length($r)){
                        $r = $nowstr;
                        last;     
           }

        }
    }
        return  $r;
}

当然用到length函数的可以先定义一个标量,这样不会每次循环时都调用length.
你可以在你写的子例程里加入红色的print $nowstr,然后比较看一下我改的,可以发现到两个字符串很长的时候循环次数的差别.

你楼下的用正则的循环次数最少.
以上供参考
作者: surfybeach    时间: 2009-03-12 06:34
或者可以读读cpan模块 Algorithm::Diff 的源码，函数LCS就是干这个的，求最长公共子串。

[ 本帖最后由 surfybeach 于 2009-3-12 06:39 编辑 ]
作者: xiaojao    时间: 2009-03-31 17:34
原帖由 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    时间: 2010-05-27 14:33
回复 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    时间: 2010-05-27 15:26
本帖最后由 iamlimeng 于 2010-05-27 15:35 编辑

开始理解错误，纠正一下。
作者: wxlfh    时间: 2010-05-27 16:33
有个不算BUG的BUG，当有两个都符合条件时，只能求出其中一个字符串，比如：
my $str1 = '123456abcd';
...
xiaojao 发表于 2009-03-31 17:34



    的确，我这个东西很不成熟。
作者: iamlimeng    时间: 2010-05-27 16:58
我开始也是有这个疑惑，若有多个公共子串，应该如何计算。我在wxlfh代码基础上改了一下，能获得长度大于2的公共子串：
  1. #!/usr/bin/perl

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

  33. my $str1 = '123456abcdefeeeee';
  34. my $str2 = '234dddabcdegeeee';
  35. $str = max_mutual_str($str1,$str2);
  36. print "$str\n";
复制代码
输出：234 abcde eeee

我加了显示计算过程的代码。以上代码可能不够简洁，等高手指点。
作者: blackold    时间: 2010-05-27 17:41
本帖最后由 blackold 于 2010-05-28 09:54 编辑
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;

  5. my $str1 = ...;
  6. my $str2 = ...;
  7. my $str = $str1 . "\n" . $str2;

  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    时间: 2010-05-27 23:33
回复 37# blackold


这个代码太帅了。

可能需要小改一下，输出很接近正确结果了，但还得不到完全正确的结果。
作者: blackold    时间: 2010-05-28 09:37
回复 38# iamlimeng


    代码不规范，结果应该是对的(假设字符串不包含\n)啊？
作者: iamlimeng    时间: 2010-05-28 09:43
回复 39# blackold


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

输出：
dddab
abcde

末尾的eeee没有输出

LZ再调试一下程序。
作者: blackold    时间: 2010-05-28 09:47
本帖最后由 blackold 于 2010-05-28 10:09 编辑

回复 40# iamlimeng


    晕。我不是LZ吧？

   只输出最长的公共子串，eeee没有 dddab和 abcde"长"吧？
作者: iamlimeng    时间: 2010-05-28 09:52
回复 41# blackold


明白了，如果是求最长的，那就对了。学习了，消化一下。
作者: Cu_fans    时间: 2010-05-31 10:14
blackold 发表于 2010-05-27 17:41



   
$str =~ /(.+)(?=.*\n.*\1)/g

有没哪位解释下这个正则表达式的意思啊？
作者: liyangole    时间: 2010-05-31 13:43
回复 4# wxlfh


    赞
作者: liyangole    时间: 2010-05-31 13:51
回复 2# khandielas


    这个实现了每个字符的相同的方式，还是有点疑问，关于 %hash2 的作用。
作者: liyangole    时间: 2010-05-31 15:02
回复 37# blackold


    赞，有不明请教，my @substr =  sort { length($b) <=> length($a) } $str =~ /(.+)(?=.*\n.*\1)/g;

                            my @result = grep { length == length $substr[0]} @substr;
    讲述一下，不胜感谢。
作者: blackold    时间: 2010-05-31 15:18
回复 46# liyangole


    都是sort grep的基本用法啊，具体哪些不清楚？
作者: blackold    时间: 2010-05-31 15:20
回复 43# Cu_fans


    零宽断言。
作者: liyangole    时间: 2010-05-31 15:25
$str =~ /(.+)(?=.*\n.*\1)/g
这个正则，解释一下，谢谢。
作者: liyangole    时间: 2010-05-31 15:30
回复 48# blackold


    您的解释，恕我愚钝，不能理解，可否详细讲。
作者: blackold    时间: 2010-05-31 15:35
就是一个或多个非\n字符，后接0个或多个非\n字符，后接\n, 后接0个或多个非\n字符，再后接红色部分所匹配的字符串，蓝色部分是零宽断言。

说得挺啰嗦的。
作者: liyangole    时间: 2010-05-31 15:41
回复 51# blackold


    了解了，多谢，对这个 零宽断言，还是第一次听说！
作者: buaaspy    时间: 2010-06-09 19:30
哪位神牛写个后缀数组版本的~~
作者: 黑色阳光_cu    时间: 2010-07-22 17:58
  1. #!/bin/env perl

  3. use strict;
  4. use warnings;

  6. my $s1 = 'asdfdfdfdfdfdfdfdfdfasf34lk343434343433333fdasfd';
  7. my $s2 = 'asdfdfdfdfdfdfdfdfdf3434343434343jfshasdazlzlasbfasf';

  9. warn max_mutual_str($s1, $s2);

  11. sub max_mutual_str
  12. {
  13.         my ($cnt_offest, $cnt_length) = (0, 1);
  14.         my ($substr_offest, $substr_length) = (0, 0);
  15.         my $str_length = length($_[0]);

  17.         while ($str_length - $cnt_offest > $substr_length)
  18.         {
  19.                 if (index($_[1], substr($_[0], $cnt_offest, $cnt_length)) == -1)
  20.                 {
  21.                         ++$cnt_offest;
  22.                 }
  23.                 else
  24.                 {
  25.                         if ($substr_length < $cnt_length)
  26.                         {
  27.                                 ($substr_offest, $substr_length) = ($cnt_offest, $cnt_length);
  28.                         }
  29.                        
  30.                         ++$cnt_length;
  31.                 }
  32.         }

  34.         return substr($_[0], $substr_offest, $substr_length);
  35. }

复制代码
作者: bintre    时间: 2010-07-23 08:46
好厉害！！
作者: dahe_1984    时间: 2010-08-04 17:09
作者: huanhuolang    时间: 2010-08-14 17:21
牛啊~~~~~~~~
作者: aaronvox    时间: 2010-08-14 17:33
看完了得顶
作者: gongyonghui2    时间: 2012-11-24 15:54
回复 37# blackold


my $str1 ="aab12345678";
my $str2 = "ab1234yb1234567";
会给出错误答案:ab1234
正则思想很好，只是忽略了正则匹配的方式并非逐字符前进匹配:一但匹配成功就跳到该位置末尾继续匹配。
作者: gis11rj    时间: 2012-11-24 17:12
khandielas 发表于 2008-12-14 06:33
楼主写的象Perl写的C 程序

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


这个虽然能找到相同的一个字符，可是如果不相邻，也会得到，跟题目的要求好像还差点儿～～
作者: minority    时间: 2012-11-25 19:41
machine 发表于 2008-12-15 09:01
我这个算法，用的是一个比较老套的lcs算法。以前用c写过，在perl下又模仿实现了一下。

算法大概描述就 ...

算法不错！！！！
作者: mcshell    时间: 2012-11-26 11:23
回复 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    时间: 2012-11-27 00:02
回复 59# gongyonghui2


    多谢指正!

    确实如你所说，原来的代码是错误的。try：
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;

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

  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    时间: 2012-11-27 00:13
回复 62# mcshell


    学习！
作者: mcshell    时间: 2012-11-27 00:18
回复 64# blackold


    黑哥太谦虚了   多向黑哥请教才是
作者: hzy2hzy    时间: 2012-11-27 17:33
machine 发表于 2008-12-15 09:01
我这个算法，用的是一个比较老套的lcs算法。以前用c写过，在perl下又模仿实现了一下。

算法大概描述就 ...


赞算法！
作者: gongyonghui2    时间: 2012-11-28 11:52
回复 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    时间: 2012-11-28 12:07
回复 67# gongyonghui2


  好!
学习!
作者: qinyudd    时间: 2012-11-28 13:58
  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);

  36. }
复制代码
二分法
如果公共子串较长有奇效
作者: anders0913    时间: 2012-11-28 14:34
machine 发表于 2008-12-15 09:01
我这个算法，用的是一个比较老套的lcs算法。以前用c写过，在perl下又模仿实现了一下。

算法大概描述就 ...


学习了
作者: rubyish    时间: 2013-01-22 09:29
不得不赞一个。
那个效率更高？ 高手能否帮分析一下。
作者: blackfur    时间: 2013-03-03 03:50
#!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    时间: 2013-03-06 09:22
作者: xo1980    时间: 2013-03-06 09:22
作者: zzwevil    时间: 2013-03-07 19:18
应该是很笨的方法吧，但是也想了好久，不知道效果如何，有人愿意帮忙测试吗？
#!/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";
作者: 方兆国儿    时间: 2013-03-07 19:40
@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. }

  16. $str1 = '369abcdefg/789';
  17. $str2 = '123bcdefg/0147123';
  18. $str = max_mutual_str($str1,$str2);
  19. print "\t$str\n";
复制代码
向大神学习
作者: gdw1986    时间: 2013-07-19 20:34
回复 4# wxlfh

请问你这种算法不存在遗漏吗，你的应该都是比如取abcd不行的话就到abc每次都是从前面取的吧，存不存在这种比如刚好和bcd匹配的情况被遗漏呢，菜鸟问的
   
作者: a448677947    时间: 2015-02-13 11:29
本帖最后由 a448677947 于 2015-02-13 12:15 编辑

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    时间: 2015-07-02 15:02
本帖最后由 david_95 于 2015-07-02 16:30 编辑

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

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



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2