经典题，没做过的做做看

teebye

写个算法，求最长公共子序列

比如2个字符串A="chinese is great" B ="chinese is all kind" ,那么A和B的最长公共子序列就是chinese is

[ 本帖最后由 teebye 于 2009-3-25 11:33 编辑 ]

daybreakcx

LCS问题，貌似结果应该是"chinese is "如果我没看错

zhenglxd

原帖由 teebye 于 2009-3-25 10:03 发表
写个算法，求最长公共子序列

比如2个字符串A="chinese is great" B ="chinese is all kind" ,那么A和B的最长公共子序列就是chinese

...初学拙作

def com_subseq(a,b):     a=a.split()     b=b.split()     c=[i for i in a if i in b]     l=len(c)     for i in xrange(l):         c[i]=str(c[i]).strip()     for i in xrange(l):         if len(c[0])<len(c[i]):             c[0],c[i]=c[i],c[0]     return c[0] if __name__=="__main__":     A="chinese is great"     B ="chinese is all kind"     print com_subseq(A,B)

caesarok

def com_subseq(a,b):
    a=a.split()
    b=b.split()
    c=[i for i in a if i in b]
    l=len(c)
    for i in xrange(l):
        c=str(c).strip()
    for i in xrange(l):
        if len(c[0])<len(c):
            c[0],c=c,c[0]
    return c[0]

if __name__=="__main__":
    A="chinese is great"
    B ="chinese is all kind"
    print com_subseq(A,B)
            

看这样会不会好些

1. 
   
2. 
   
3. for i in xrange(1):
   
4.         if len(C[i])>len(C[0]):
   
5.                 return C [i]
   
6.         else:
   
7.                 return C[0]
   

复制代码

[ 本帖最后由 caesarok 于 2009-3-25 11:16 编辑 ]

zhenglxd

原帖由 caesarok 于 2009-3-25 11:15 发表

看这样会不会好些


for i in xrange(1):
        if len(C)>len(C[0]):
                return C
        else:
                return C[0]

看不懂你写的啊

能写完整点不？

daybreakcx

def LCS(a,b):     s=[[0 for x in range(len(b)+1)],[0 for x in range(len(b)+1)]]     last=0     res=0     resto=0     for i in range(len(a)):         for j in range(len(b)):             if (a[i]==b[j]) :                 s[1-last][j+1]=s[last][j]+1             else:                 s[1-last][j+1]=max(s[1-last][j],s[last][j])             if (s[1-last][j+1]>res):                 res=s[1-last][j+1]                 resto=j         last=1-last     return b[resto-res+1:resto+1] a="chinese is great" b="chinese is all kind" print(LCS(a,b))

个人还是坚持认为如果是经典题楼主把题目讲错了，应该最长公共子序列是"chinese is "，长度是11

daybreakcx

def LCS(a,b):     a=a.split()     b=b.split()     res=""     for x in a:         for y in b:             if (x==y) and (len(x)>len(res)):                 res=x     return res a="chinese is great" b="chinese is all kind" print(LCS(a,b))

按照你的思路程序这样就可以了，输出是"Chinese"

zhenglxd

原帖由 daybreakcx 于 2009-3-25 11:28 发表
def LCS(a,b):
    s=[[0 for x in range(len(b)+1)],[0 for x in range(len(b)+1)]]
    last=0
    res=0
    resto=0
    for i in range(len(a)):
        for j in range(len(b)):
            if  ...

报告 遇到意外情况

你把a="chinese is great all kind eng a"
b="chinese is all kind eng w"
带入实验下

结果是 s all kind eng

daybreakcx

def LCS(a,b):     s=[[0 for x in range(len(b)+1)],[0 for x in range(len(a)+1)]]     last=0     res=0     for i in range(len(a)):         for j in range(len(b)):             if (a[i]==b[j]) :                 s[1-last][j+1]=s[last][j]+1             else:                 s[1-last][j+1]=max(s[1-last][j],s[last][j+1])             if (s[1-last][j+1]>res):                 res=s[1-last][j+1]         last=1-last     return res a="chinese is great all kind eng a" b="chinese is all kind eng w" print(LCS(a,b))

是我错了，不该直接输出那个串，LCS如果要输出那个串中间是要记录的，而且是非连续的，但是长度绝对是没错的，是24
那个被提取出来的串是"Chinese is all kind eng ",正好24，操作是把a的" great"和"a"删掉，b的"w"删掉就可以了