最长公共子串- 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实现算法:

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

php实现

<?php
function test($str1, $str2)
{
    //创建一个数组
    $data = [];
    $str1Arr = mb_str_split($str1);//中文切割数组
    $str2Arr = mb_str_split($str2);//中文切割数组
    $maxNum = 0;//最大字符串长度
    $maxLocation = [];//最大字符串长度坐标
    foreach ($str1Arr as $k1 => $v1) {
        foreach ($str2Arr as $k2 => $v2) {
            //如果值相同
            if ($v1 == $v2) {
                //判断之前的字符串是否存在
                if (isset($data[$k1 - 1][$k2 - 1])) {
                    $data[$k1][$k2] = 1 + $data[$k1 - 1][$k2 - 1];
                } else {
                    $data[$k1][$k2] = 1;
                }
                if ($maxNum < $data[$k1][$k2]) {
                    $maxNum = $data[$k1][$k2];
                    $maxLocation = [$k1, $k2];
                }
            } else {
                $data[$k1][$k2] = 0;
            }
        }
    }
    if (empty($maxLocation)) {
        $str = '';
    } else {
        $str = '';
        $i = $maxLocation[0];
        $j = $maxLocation[1];
        while (1) {
            if (empty($data[$i][$j])) {
                break;
            }
            $str = $str1Arr[$i] . $str;//因为获取到的字符串是最后一位,所以要反向拼接
            $i--;
            $j--;
        }
    }
    return $str;
}
function mb_str_split($str){
    return preg_split('/(?<!^)(?!$)/u', $str );
}
$a = test('123456789', '98712345324');
echo $a;