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)