最长公共子串- LCS 算法

#!/usr/bin/python
# coding:utf-8
def action (str1,str2):
    pass
    #转为utf-8编码,一个中文字长度占用1
    str1 = str1.decode("utf-8")
    str2 = str2.decode("utf-8")
    data = {}
    maxNum = 0
    maxLocation = []
    #根据长度遍历2个字符串
    for i in range(len(str1)):
        for j in range(len(str2)):
            v1 = str1[i]
            v2 = str2[j]
            #如果v1等于v2,则该坐标值+1
            if v1==v2 :
                if data.has_key(i)==False:
                    data[i] = {}
                data[i][j] = 1;
                # 判断上一个斜线是否已经是相等了,如果是,则增加上上次的值
                if (data.has_key(i-1)) and (data[i-1].has_key(j-1)) :
                    data[i][j] += data[i-1][j-1]
                # 修改最大坐标跟最大数值
                if data[i][j]>maxNum:
                    maxNum = data[i][j]
                    maxLocation = [i,j]

    str = ""
    i = maxLocation[0]
    j = maxLocation[1]
    while True :
        if i<0 or j<0:
            break
        if (data.has_key(i)==False) or (data[i].has_key(j)==False) :
            break
        str = str1[i]+str
        print i,j
        i-=1
        j-=1

    print str,data

result = action("123231aaa测试","12aa测试")