LCS，给你一个不一样的模糊匹配

LCS(longest-common-subsequence problem),又名最长公共子序列问题
给定两个序列X和Y，如果Z既是X的子序列，也是Y的子序列，我们称它为X和Y的公共子序列

比如X={A,B,C,D,E,F,G} Y={T,A,C,M,G}，那么Z={A,C,G}，就是其最长公共子序列
复制代码

2. 为什么说需要LCS来解决模糊匹配

我们一般的字符串匹配，就是子串查找；但是实际应用中，往往有子串查找解决不了的问题；
比如『我家有台电视机，你要不』和『我有个电视机，你要不』这两者其实指代同一个事情；
那么在实际应用场景中，特别是工业领域，往往无法存在严格的子串和母串；
更多的是相似性问题，即相似的字符串指代同一个物品/事件。
复制代码

3. 实现原理

最长公共子序列问题:给定两个序列
X={X1,X2,...,Xm} Y={Y1,Y2,...,Yn},求X和Y长度最长的公共子序列。
复制代码

好了，我们想一想，假设这是个算法题，我们会怎么做？

第一反应可能是穷举扫描，但是呢，我们也知道，如果字符串太长，暴力方法运行的时间是我们不能忍受的。

然后我们又会想到，将大问题拆分成小问题，用递归的思想解决。

我们假设：
1.Xm=Yn,那么X,Y的最长公共子序列，肯定会包含最后这个字符，那么就变成求解Xm-1,Ym-1的LCS
2.Xm!=Yn,这个时候，如果最长公共子序列不含Xm,就意味着，该题变成求解Xm-1和Yn的公共子序列
3.Xm!=Yn,这个时候，如果最长公共子序列不含Yn,就意味着，该题变成求解Xm和Yn-1的公共子序列
复制代码

至此为止，我们找到了求解最长公共子序列的方法。

我们仔细观察一下上述的分析过程，是不是似曾相识？ 这正是 问题！

让我们来回顾一下什么是动态规划：

动态规划通常用来求解最优化问题
动态规划是通过组合子问题的解来解决原问题
....
复制代码

以及观察某个问题，是否适用于动态规划算法：

1.是否具有最优子结构性质
    如果一个问题的最优解，包含其子问题的最优解
2.具有重叠子问题性质
    问题的递归算法会反复求解相同的子问题
复制代码

详见 《什么是动态规划》 一章

好了，接着说回LCS，通过上述的分析，我们得到如下的公式：

为什么公式是如上形式？因为我们假设X，Y串如下排列，像是一个二维数组

其中X={A,B,C,A,D,A,B} Y={B,A,C,D,B,A}

C[i][j]代表公共子序列的长度

如果Xi=Yj,那么意味着子序列又多匹配上一位，其在Xi-1,Yj-1的最长公共子序列的结果上多增加了一个。

如果Xi!=Yj,那么意味着，Xi,Yj的最长公共子序列的答案肯定在Xi-1，Yj或者Xi,Yj-1的最长公共子序列中，那么既然是最长，肯定是取两者中更大的值；

至此，我们已经清晰的定义出LCS的求解公式。

按照这个公式，我们可以自顶向下的递归或者自底向上的累加；一般动态规划，采用自底向下更简单些；

思路如下：

int nLenX = X.length();
int nLenY = Y.length();
char** C = new char[nLenX + 1][nLenY + 1];

//初始化c二维数组
....

//LCS
for ( int i = 1; i <= nLenX; i++ )
{
    for ( int j = 1; j <= nLenY; j++ )
    {
        if ( X[i-1] == Y[j-1])
        {
            C[i][j] = C[i-1][j-1] + 1;
        }
        else if ( C[i-1][j] >= C[i][j-1] )
        {
            C[i][j] = c[i-1][j];
        }
        else
        {
            C[i][j] = C[i][j-1];
        }
    }
}

//析构数组
复制代码

按照公式实现就行了，很简单

这里有个小细节。C[][]下标是从1开始的，并且长度比X，Y要长1位，这是从实现角度，省下了考虑i-1 < 0的问题，实现的一个小技巧。

如下图所示：

目前为止，我们确实是实现了LCS,但是如何输出该最长子串呢？

很简单，只要在上述代码中，对其走过的字串进行标记，标记后通过反向递归，得到路径，如上图所示的灰色箭头就是其回溯的路径。

其他相关章节
复制代码