【iOS重学】从LCS到IGListKit框架中的Diff算法（上）

什么是LCS

子序列

假设有两个序列 X, Z：

$X = <x_1,x_2,x_3,……x_m>$

$Y = <y_1,y_2,y_3,……y_n>$

若 Z 序列中的每个元素都能在 X 中找到，并且是严格递增的，那么就称 Z 是 X 的子序列。

公共子序列

Z 既是 X 的子序列，也是 Y 的子序列，则称 X，Y 的公共子序列是 Z，公共子序列长度为元素的个数。

最长公共子序列

最长公共子序列（Longest Common SubSequence），简称 LCS，指的是两个序列中元素个数最多的公共子序列。

$LCS$的广泛应用

LCS 是一个经典的计算机科学问题，也是数据比较程序，LCS主要应用在：

Git等版本控制中文件的对比
一些做图片、文件、文本等对比的软件
IGListKit框架中的Diff算法来做UICollectionView的刷新

如何求两个序列的$LCS$

给定两个序列：

$X = <x_1,x_2,x_3,……x_m>$

$Y = <y_1,y_2,y_3,……y_n>$

求 X，Y 的最长公共子序列。

蛮力算法

依次检查 X 中的每个子序列在 Y 中是否出现。

时间复杂度：$O(n2^m)$

分析：这个时间复杂度是一个指数级，很明显这个算法是不合适的。

动态规划算法

一、子问题界定

假设 X 序列终止位置为 $i$ ，Y 序列终止位置为 $j$ ：

$X = <x_1,x_2,x_3,……x_i>$

$Y = <y_1,y_2,y_3,……y_j>$

如图所示：

2022060901

二、子问题之间的依赖关系

设$X = <x_1,x_2,x_3,……x_m>$，$Y = <y_1,y_2,y_3,……y_n>$

$Z = <z_1,z_2,z_3,……z_k>$ 为 X 和 Y 的 LCS，那么：

（一）如果$x_m = y_n$ => $z_k = x_m = y_n$，则$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的 LCS，如下图所示：

2022060902

（二）如果$x_m \neq y_n$，$z_k \neq x_m$ => $Z$ 是 $X_{m-1}$ 和 $Y_n$ 的 $LCS$，如下图所示：

2022060903

（三）如果$x_m \neq y_n$，$z_k \neq y_n$ => $Z$ 是 $X_m$ 和 $Y_{n-1}$的 $LCS$，如下图所示：

2022060904

三、递推方程

$X$ 与 $Y$ 的子序列：

$X_i = <x_1,x_2,x_3,……x_i>$

$Y_j = <y_1,y_2,y_3,……y_j>$

$DP[i,j]$是$X_i$ 和 $Y_j$ 的 $LCS$ 的长度，由此我们可以得到递推方程为：
$$
DP[i,j] =
\begin{cases}
0,&若i = 0 或 j = 0\
DP[i-1,j-1]+1, &若i,j > 0,x_i = y_j\
max{DP[i,j-1],Dp[i-1,j]}, &若 x,j = 0, x_i \ne y_j
\end{cases}
$$

求解$LCS$的具体实例

例1：两个序列

$X = <A,D,F,G,T>$

$Y = <A,F,O,X,T>$

求 $X$ 和 $Y$ 的$LCS$

2022060905

可以得到$X$ 和 $Y$ 的 $LCS$ 为：$<A,F,T>$，长度为3。

具体求解算法如下：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]);
                dp[i][j] = Math.max(dp[i][j - 1], dp[i][j]);
            }
        }
        return dp[m][n];
    }
}