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

bandaotidejia

微软还用perl？

面试 面世

iakuf

人家当时的要求是，无论你用什么方法来写

mfzz1134

经典DP,开矩阵是对地,效率最高.

wxlfh

Perl中可能效率不是最高也说不定。

cheveu

我是外行，不会编程。
不过，不知道“卷积”可行不？

junonly

perl 新手, 写个试试

1. 
   
2. #!/usr/bin/perl
   
3. 
   
4. &max_index_of_two_string('xabcdxxxveafa', 'eabcafeveafaeagagade');
   
5. 
   
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

my $str = $str1;
        $str1 = $str2;
        $str2 = $str;
标准c语言写法。
perl 写法：
($str1,$str2)=($str2,$str1);

junonly

原帖由 machine 于 2009-1-6 10:36 发表
my $str = $str1;
        $str1 = $str2;
        $str2 = $str;
标准c语言写法。
perl 写法：
($str1,$str2)=($str2,$str1);

这样就可以swap了，又学到新东西啊。

grubbyoo

俺用 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

原帖由 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,然后比较看一下我改的,可以发现到两个字符串很长的时候循环次数的差别.

你楼下的用正则的循环次数最少.
以上供参考