最长公共子串- LCS 算法

 LCS (Longest Common Subsequence) 算法

已知字符串str1="网站高并发解决方案",str2="如何解决网站高并发",如何字符串最长公共子串?

lcs 算法原理

将2个字符串采用行列 排列:

	如	何	解	决	网	站	高	并	发
网
站
高
并
发
解
决
方
案

如果行列里面的字符相同,则表示1,否则为0:

	如	何	解	决	网	站	高	并	发
网	0	0	0	0	1	0	0	0	0
站	0	0	0	0	0	1	0	0	0
高	0	0	0	0	0	0	1	0	0
并	0	0	0	0	0	0	0	1	0
发	0	0	0	0	0	0	0	0	1
解	0	0	1	0	0	0	0	0	0
决	0	0	0	1	0	0	0	0	0
方	0	0	0	0	0	0	0	0	0
案	0	0	0	0	0	0	0	0	0

同时我们可以优化: 很明显,通过坐标可看到,相同的坐标已经标位1,通过计算连续对角线长度,即可比对出最长字符串.

如果行列里面的字符不相同,则表示为0,否则表示为 该坐标左上角的值后再加1:

	如	何	解	决	网	站	高	并	发
网	0	0	0	0	1	0	0	0	0
站	0	0	0	0	0	2	0	0	0
高	0	0	0	0	0	0	3	0	0
并	0	0	0	0	0	0	0	4	0
发	0	0	0	0	0	0	0	0	5
解	0	0	1	0	0	0	0	0	0
决	0	0	0	2	0	0	0	0	0
方	0	0	0	0	0	0	0	0	0
案	0	0	0	0	0	0	0	0	0

在判断字符串时,记录当前最大值与当前最大值坐标,判断完毕之后,即可通过记录的最大坐标获取到最长字符串最后的坐标值

python实现算法:

代码语言：javascript复制

#!/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测试")

本文为仙士可原创文章,转载无需和我联系,但请注明来自仙士可博客www.php20.cn

压力测试 编程算法

0 人点赞