天下

记录修行的印记

动态规划算法(4):lcs递归算法python的实现

#coding:gbk
import os,sys
def lcs(short, long):
    m 
= len(short)
    n 
= len(long)
    
if (m <= 0 or n <= 0):
        
return "";
    
if m>n:
        short,long 
= long,short

    
if short in long:
        
return short
    t1 
= lcs(short[1:],long)
    t2 
= lcs(short[0:-1],long)
    
if t1>t2:
        
return t1
    
else:
        
return t2


def main():
    
if len(sys.argv)<3:
        
print "使用:lcs <字符串1> <字符串2>"
        
return
    a 
= lcs(sys.argv[1],sys.argv[2])
    
print "最大公共子串长度:%d"%len(a)
    
print "最大公共子串:"+a
if __name__ == '__main__':
    main()

posted on 2013-03-21 19:01 天下 阅读(1104) 评论(1)  编辑 收藏 引用 所属分类: Python算法

评论

# re: 动态规划算法(4):lcs递归算法python的实现[未登录] 2013-06-17 01:32 charles

LCS的意思是Longest Common Sequence,not string,而且你这也不是dynamic program的方法,不懂不要乱起标题。误人子弟啊!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(4)

随笔分类(378)

随笔档案(329)

链接

最新随笔

搜索

最新评论