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

bleem1998

UID: 272
帖子: 63
积分: 144
在线时间: 5 小时

1^# bleem1998 发表于 2008-12-30 11:15

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

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

[Copy to clipboard] [ - ]

CODE:

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

感觉挺有难度的

xiaoyu9805119

UID: 39268
帖子: 67
积分: 154
在线时间: 6 小时

2^# xiaoyu9805119 发表于 2008-12-30 13:03

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

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

爱知

UID: 35074
帖子: 1
积分: 2
在线时间: 10 分钟

3^# 爱知发表于 2008-12-30 13:12

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

[Copy to clipboard] [ - ]

CODE:

#!/usr/bin/env python

from sys import argv, exit

def find_max_substr(a, b):
position = 0
lengh = 0

for i in range(len(a)):
for j in range(len(b)):
ii = 0; jj = 0;
while(a[i+ii] == b[j+jj]):
ii += 1; jj += 1;
if i+ii > len(a)-1 or j+jj > len(b)-1: break
if(jj > lengh):
position = i; lengh = jj;

print a[position:position+lengh]

if __name__ == '__main__':
if len(argv) < 3:
print "Usage: cmd str1 str2"
exit(1)
find_max_substr(argv[1], argv[2])

xiaoyu9805119

UID: 39268
帖子: 67
积分: 154
在线时间: 6 小时

4^# xiaoyu9805119 发表于 2008-12-30 13:38

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

anbutu

UID: 22114
帖子: 87
积分: 200
在线时间: 10 小时

5^# anbutu 发表于 2008-12-30 17:02

Dynamic programming

efhilt

UID: 38186
帖子: 11
积分: 25
在线时间: 10 分钟

6^# efhilt 发表于 2008-12-31 02:42

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

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

[Copy to clipboard] [ - ]

CODE:

def substr_gen(s):
if len(s) == 1:
      yield s
      raise StopIteration
else:
      yield s
      for i in substr_gen(s[1:]):
         yield i
      for i in substr_gen(s[:-1]):
         yield i

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

下面就是分析。

[Copy to clipboard] [ - ]

CODE:

String A :　　 AAAAAAA
String B: BBB
投影 : X

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

下面还是一个generator

[Copy to clipboard] [ - ]

CODE:

def string_pair_gen(s1, s2):
length = len(s1) + len(s2) - 1
_s1 = '\0' * (length - len(s1)) + s1
_s2 =  s2 + (length - len(s2)) * '\0'

while len(_s1) != 0:
      yield _s1, _s2
      _s1 = _s1[1:]
      _s2 = _s2[:-1]

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

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

emacsnw

UID: 41431
帖子: 80
积分: 184
在线时间: 9 小时

7^# emacsnw 发表于 2008-12-31 03:59

这不是传说中的 LCS 吗

softy

UID: 33839
帖子: 1
积分: 2
在线时间: 10 分钟

8^# softy 发表于 2008-12-31 04:55

def lcs(long, short):
if short in long:
   return short
s1 = lcs(long, short[:-1])
s2 = lcs(long, short[1:])
if len(s1) > len(s2):
   return s1
else:
   return s2

网上的,递归,不过,好像字符稍微长点,python就处理不了

softy

UID: 33839
帖子: 1
积分: 2
在线时间: 10 分钟

9^# softy 发表于 2008-12-31 04:56

def findRow0(m, n, A, B):
print "findRow0", m , n , ''.join(A), ''.join(B)
K0 = []
K1 = [0] * (n+1)
# in PDF, this lien is 1:n, It may be wrong
for i in range(0,m):
      K0 = K1[:]
      for j in range(0,n):
         #print i, j
         if A == B[j]:
            K1[j+1] = K0[j] +1
         else:
            K1[j+1] = max ( K1[j], K0[j+1])

LL = K1
print 'LL =', LL
return LL

def H_LCS0(m, n, A, B):
print "H_LCS0", m, n, ''.join(A), ''.join(B)
if n == 0:
      C = []
elif m == 1:
      if A[0] in B:
         C = [A[0]]
      else:
         C = []
else:
      i = m / 2
      #step3
      L1 = []
      A1i = A[0:i]
      L1 = findRow0(i, n, A1i, B)


      Anip1 = A[i:]
      Anip1.reverse()
      Bn1 = B[:]
      Bn1.reverse()
      L2 = findRow0(m-i, n, Anip1, Bn1)

      #step4
      M = 0
      k = 0
      for j in range(0, n+1):
         tmp = L1[j] + L2[n-j]
         if tmp > M:
            M = tmp
            k = j

      #step 5
      print 'i=', i, 'k=', k, 'm=', m, 'n=', n
      C1 = H_LCS0( i, k, A[0:i], B[0:k])

      C2 = H_LCS0( m-i, n-k, A[i:], B[k:])
      #step 6
      C = C1+ C2
      print "C1=",  ''.join(C1), "C2=", ''.join(C2),
print "C = ", ''.join(C)
return C

A = "ACGTACGTACGT"
B = "AGTACCTACCGT"
C = H_LCS0(len(A), len(B), list(A), list(B))
print "final result", ''.join(C)

http://blog.csdn.net/pkrobbie/archive/2007/10/10/1818477.aspx

爱知

UID: 35074
帖子: 1
积分: 2
在线时间: 10 分钟

10^# 爱知发表于 2008-12-31 11:40

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

功夫不够，尚需努力

^_^