LCS

LCS 命令实现了最长公共子序列算法。请注意，这与最长公共子串算法不同，因为字符串中的匹配字符不需要是连续的。

例如，“foo”和“fao”之间的 LCS 是“fo”，因为从左到右扫描这两个字符串时，最长的共同字符集由第一个“f”和“o”组成。

LCS 对于评估两个字符串的相似度非常有用。字符串可以代表许多事物。例如，如果两个字符串是 DNA 序列，LCS 将提供衡量这两个 DNA 序列相似度的标准。如果字符串代表用户编辑的某些文本，LCS 可以表示新文本与旧文本的差异程度，等等。

请注意，此算法的运行时间复杂度为 O(N*M)，其中 N 是第一个字符串的长度，M 是第二个字符串的长度。因此，要么启动一个不同的 Valkey 实例来运行此算法，要么确保它针对非常小的字符串运行。

> MSET key1 ohmytext key2 mynewtext
OK
> LCS key1 key2
"mytext"

有时我们只需要匹配的长度

> LCS key1 key2 LEN
(integer) 6

然而，通常非常有用的，是知道每个字符串中的匹配位置

> LCS key1 key2 IDX
1) "matches"
2) 1) 1) 1) (integer) 4
         2) (integer) 7
      2) 1) (integer) 5
         2) (integer) 8
   2) 1) 1) (integer) 2
         2) (integer) 3
      2) 1) (integer) 0
         2) (integer) 1
3) "len"
4) (integer) 6

匹配是从最后一个到第一个生成的，因为这是算法的工作方式，并且以相同的顺序发出内容效率更高。上面的数组意味着第一个匹配（数组的第二个元素）是在第一个字符串的 2-3 位置和第二个字符串的 0-1 位置之间。然后是 4-7 和 5-8 之间的另一个匹配。

将匹配列表限制为给定最小长度的匹配

> LCS key1 key2 IDX MINMATCHLEN 4
1) "matches"
2) 1) 1) 1) (integer) 4
         2) (integer) 7
      2) 1) (integer) 5
         2) (integer) 8
3) "len"
4) (integer) 6

最后，也要获取匹配长度

> LCS key1 key2 IDX MINMATCHLEN 4 WITHMATCHLEN
1) "matches"
2) 1) 1) 1) (integer) 4
         2) (integer) 7
      2) 1) (integer) 5
         2) (integer) 8
      3) (integer) 4
3) "len"
4) (integer) 6

RESP2 回复

以下之一

• Bulk string reply (批量字符串回复)：最长公共子序列。

• Integer reply (整数回复)：当给出 LEN 时，最长公共子序列的长度。

• Array reply (数组回复)：当给出 IDX 时，一个包含 LCS 长度和两个字符串中所有范围的数组。

RESP3 回复

以下之一

• Bulk string reply (批量字符串回复)：最长公共子序列。

• Integer reply (整数回复)：当给出 LEN 时，最长公共子序列的长度。

• Map reply (映射回复)：当给出 IDX 时，一个包含 LCS 长度和两个字符串中所有范围的映射。