pythonは3つの文字列の共通文字列の長さの問題を解決します
2232 ワード
A、B、Cは、同じ定数サイズのアルファベットから取られた3つの長さnの文字列とする.3つの列の最も長い共通のサブ列を探し出すO(n^3)の時間アルゴリズムを設計する
'''
Created on 2013-6-28
@author: fpc
'''
def max1(m,n):
if(m>n):
return m
else:
return n
def max2(x,y,z,k,m,n):
a=max1(x,y)
b=max1(z,k)
c=max1(m,n)
d=max1(a,b)
e=max1(c,d)
return e
def LCSThreeLength(str1,str2,str3):
length1=len(str1)
length2=len(str2)
length3=len(str3)
c=[[[0 for k in range(length3+1)] for j in range(length2+1 )]for i in range(length1+1)]
for i in range(0,length1+1):
for j in range(0,length2+1):
c[i][j][0]=0
for j in range(0,length2+1):
for k in range(0,length3+1):
c[0][j][k]=0
for i in range(0,length1+1):
for k in range(0,length3+1):
c[i][0][k]=0
for i in range(1,length1+1):
for j in range(1,length2+1):
for k in range(1,length3+1):
if str1[i-1] == str2[j-1] and str1[i-1]==str3[k-1]:
c[i][j][k] = c[i-1][j-1][k-1]+1
elif str1[i-1] == str2[j-1] and str1[i-1] != str3[k-1]:
c[i][j][k] = max1(c[i-1][j-1][k],c[i][j][k-1])
elif str1[i-1] == str3[k-1] and str1[i-1] != str2[j-1]:
c[i][j][k] = max1(c[i-1][j][k-1],c[i][j-1][k-1])
elif str2[j-1] == str3[k-1] and str2[j-1] != str1[i-1]:
c[i][j][k] = max1(c[i][j-1][k-1],c[i-1][j][k])
else:
c[i][j][k] = max2(c[i-1][j][k],c[i][j-1][k],c[i][j][k-1],c[i-1][j-1][k],c[i-1][j][k-1],c[i][j-1][k-1])
length = c[length1][length2][length3]
return length
str1 = input("please input string1:")
str2 = input("please input string2:")
str3 = input("please input string3:")
length = LCSThreeLength(str1,str2,str3)
print("the common length of the three string is :",length)