最长公共子串- 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测试")

<?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;