算法之最长公共子序列(LCS)算法

比如：求下面字符串最长公共子序列

“abcbdab” 
“bdcaba”

怎么解决呢？下面就引出了本文所说的算法：LCS

一、作用

最长公共子序列常用来解决字符串的相似度

二、解决方案

• 枚举法

这种方法比较简单， 也是最容易想到的。 但是呢 ，我们要想这个问题：

一个长度为N的字符串，其子序列有2^N个，每个子序列要在第二个长度为N的字符串中去匹配，匹配一次

需要O(N)的时间，总共也就是O(N*2^N)，可以看出，时间复杂度为指数级，恐怖的令人窒息

• 动态规划

我们直接看PHP的代码实现吧,详细点的可以看 http://www.cnblogs.com/huangxincheng/archive/2012/11/11/2764625.html

function lcs($str1, $str2)
{
    // 存储生成的二维矩阵
    $dp = array();
    // 最大子串长度
    $max = 0;

    for ($i = 0; $i < strlen($str1); $i++) { 
        for ($j = 0; $j < strlen($str2); $j++) { 
            if ($str1[$i] == $str2[$j]) {
                $dp[$i][$j] = isset($dp[$i-1][$j-1]) ? $dp[$i-1][$j-1] + 1 : 1;
            } else {
                $dp[$i-1][$j] = isset($dp[$i-1][$j]) ? $dp[$i-1][$j] : 0;
                $dp[$i][$j-1] = isset($dp[$i][$j-1]) ? $dp[$i][$j-1] : 0;

                $dp[$i][$j] = $dp[$i-1][$j] > $dp[$i][$j-1] ? $dp[$i-1][$j] : $dp[$i][$j-1];
            }

            $max = $dp[$i][$j] > $max ? $dp[$i][$j] : $max;
        }
    }

    for ($i = 0; $i < strlen($str1); $i++) { 
        for ($j = 0; $j < strlen($str2); $j++) { 
            echo $dp[$i][$j] . " ";
        }
        echo "<br />";
    }

    return $max;
}

echo lcs("abcbdab", "bdcaba");