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

blackold

就是一个或多个非\n字符，后接0个或多个非\n字符，后接\n, 后接0个或多个非\n字符，再后接红色部分所匹配的字符串，蓝色部分是零宽断言。

说得挺啰嗦的。

liyangole

回复 51# blackold


    了解了，多谢，对这个 零宽断言，还是第一次听说！

buaaspy

哪位神牛写个后缀数组版本的~~

黑色阳光_cu

1. #!/bin/env perl
   
2. 
   
3. use strict;
   
4. use warnings;
   
5. 
   
6. my $s1 = 'asdfdfdfdfdfdfdfdfdfasf34lk343434343433333fdasfd';
   
7. my $s2 = 'asdfdfdfdfdfdfdfdfdf3434343434343jfshasdazlzlasbfasf';
   
8. 
   
9. warn max_mutual_str($s1, $s2);
   
10. 
    
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]);
    
16. 
    
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.         }
    
33. 
    
34.         return substr($_[0], $substr_offest, $substr_length);
    
35. }
    
36. 
    

复制代码

bintre

好厉害！！

dahe_1984

huanhuolang

牛啊~~~~~~~~

aaronvox

看完了得顶

gongyonghui2

回复 37# blackold


my $str1 ="aab12345678";
my $str2 = "ab1234yb1234567";
会给出错误答案:ab1234
正则思想很好，只是忽略了正则匹配的方式并非逐字符前进匹配:一但匹配成功就跳到该位置末尾继续匹配。

gis11rj

khandielas 发表于 2008-12-14 06:33
楼主写的象Perl写的C 程序

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

这个虽然能找到相同的一个字符，可是如果不相邻，也会得到，跟题目的要求好像还差点儿～～