Perl版有个有趣的题目：寻找最大公共串

bleem1998

原帖在此：http://bbs.chinaunix.net/thread-1333575-1-1.html

1. 
   
2. 求两个字符串的最大公共子串,是一个程序员们常常考到和想到的题目，呵呵，我用perl实现了一下,听讲是当年微软面试时要求做的一个程序,写一个返回两个任意字串中最大公共串的函数，即abcdef 和 qcfbcc 返回值为bc语言不限
   

复制代码

感觉挺有难度的

xiaoyu9805119

只是列出大概步骤和结果，没有写函数

str1 = "abcdef"
str2 = "qcfbcc/deabc"
list1 = []

min = str1
max = str2

if len(str1) > len(str2):
    min = str2
    max = str1

def cmp(x, y):
    if len(x) == len(y):
        return 0
    elif len(x) > len(y):
        return -1
    else:
        return 1

for i in range(len(min)):
    for j in range(len(min),0,-1):
        t = min[i:j]
        if t and t in max:
            list1.append(t)
        j += 1

list1.sort(cmp=cmp)
print list1

爱知

自己编了一个，只打印出第一个最长子串

1. 
   
2. #!/usr/bin/env python
   
3. 
   
4. from sys import argv, exit
   
5. 
   
6. def find_max_substr(a, b):
   
7.         position = 0
   
8.         lengh = 0
   
9.        
   
10.         for i in range(len(a)):
    
11.                 for j in range(len(b)):
    
12.                         ii = 0; jj = 0;
    
13.                         while(a[i+ii] == b[j+jj]):
    
14.                                 ii += 1; jj += 1;
    
15.                                 if i+ii > len(a)-1 or j+jj > len(b)-1: break
    
16.                         if(jj > lengh):
    
17.                                 position = i; lengh = jj;
    
18.        
    
19.         print a[position:position+lengh]
    
20. 
    
21. 
    
22. if __name__ == '__main__':
    
23.         if len(argv) < 3:
    
24.                 print "Usage: cmd str1 str2"
    
25.                 exit(1)
    
26.         find_max_substr(argv[1], argv[2])
    

复制代码

[ 本帖最后由 爱知 于 2008-12-30 13:23 编辑 ]

xiaoyu9805119

不错，不过看上去有点C的味道。

anbutu

Dynamic programming

efhilt

楼上写得太差了。这种程序能加凤爪，实在是在侮辱Python。

楼上的思路，无非是列举出一个字符串的所有字串，然后一个一个判断，是不是在另一个字符串里。要枚举出所有字串，最简单的，就是递归了。具体数学里，第一课就是递归，但是为什么到现在还有这么多人不会用。

1. 
   
2. def substr_gen(s):
   
3.     if len(s) == 1:
   
4.         yield s
   
5.         raise StopIteration
   
6.     else:
   
7.         yield s
   
8.         for i in substr_gen(s[1:]):
   
9.             yield i
   
10.         for i in substr_gen(s[:-1]):
    
11.             yield i
    

复制代码

但是这个算法有问题。那就是，那所生成的substr里面有重复。因此比较好的算法，还是LCS。不过Py有Py的风格。

下面就是分析。

1. 
   
2. String A :　　 AAAAAAA
   
3. String B:   BBB
   
4. 投影      :       X
   

复制代码

然后字符串B向右移动一位，下面的投影就变成两位了。然后以此类推，直到最后，字符串B的第一个字符同字符串A的最后一个字符重叠。

下面还是一个generator

1. 
   
2. def string_pair_gen(s1, s2):
   
3.     length = len(s1) + len(s2) - 1
   
4.     _s1 = '\0' * (length - len(s1)) + s1
   
5.     _s2 =  s2 + (length - len(s2)) * '\0'
   
6. 
   
7.     while len(_s1) != 0:
   
8.         yield _s1, _s2
   
9.         _s1 = _s1[1:]
   
10.         _s2 = _s2[:-1]
    

复制代码

这里的'\0' 是padding，因此判断投影的时候要注意。


此外，我就是shhgs。不知道flw又发什么神经了，把我的账号封了。请版主帮忙解封我的账号。

[ 本帖最后由 efhilt 于 2008-12-31 03:12 编辑 ]

emacsnw

这不是传说中的 LCS 吗 :wink:

爱知

自认为写的不好（算法，Py风格）

功夫不够，尚需努力

^_^