Python最长公共子串算法实例
本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下：
#!/usr/bin/envpython
#findanLCS(LongestCommonSubsequence).
#*publicdomain*
deffind_lcs_len(s1,s2):
m=[[0forxins2]foryins1]
forp1inrange(len(s1)):
forp2inrange(len(s2)):
ifs1[p1]==s2[p2]:
ifp1==0orp2==0:
m[p1][p2]=1
else:
m[p1][p2]=m[p1-1][p2-1]+1
elifm[p1-1][p2]<m[p1][p2-1]:
m[p1][p2]=m[p1][p2-1]
else:#m[p1][p2-1]<m[p1-1][p2]
m[p1][p2]=m[p1-1][p2]
returnm[-1][-1]
deffind_lcs(s1,s2):
#lengthtable:everyelementissettozero.
m=[[0forxins2]foryins1]
#directiontable:1stbitforp1,2ndbitforp2.
d=[[Noneforxins2]foryins1]
#wedon'thavetocareaboutthebounderycheck.
#anegativeindexalwaysgivesanintactzero.
forp1inrange(len(s1)):
forp2inrange(len(s2)):
ifs1[p1]==s2[p2]:
ifp1==0orp2==0:
m[p1][p2]=1
else:
m[p1][p2]=m[p1-1][p2-1]+1
d[p1][p2]=3#11:decr.p1andp2
elifm[p1-1][p2]<m[p1][p2-1]:
m[p1][p2]=m[p1][p2-1]
d[p1][p2]=2#10:decr.p2only
else:#m[p1][p2-1]<m[p1-1][p2]
m[p1][p2]=m[p1-1][p2]
d[p1][p2]=1#01:decr.p1only
(p1,p2)=(len(s1)-1,len(s2)-1)
#nowwetraversethetableinreverseorder.
s=[]
while1:
printp1,p2
c=d[p1][p2]
ifc==3:s.append(s1[p1])
ifnot((p1orp2)andm[p1][p2]):break
ifc&2:p2-=1
ifc&1:p1-=1
s.reverse()
return''.join(s)
if__name__=='__main__':
printfind_lcs('abcoisjf','axbaoeijf')
printfind_lcs_len('abcoisjf','axbaoeijf')
希望本文所述对大家的Python程序设计有所帮助。