LCS 公司

语法

LCS key1 key2 [LEN] [IDX] [MINMATCHLEN min-match-len] [WITHMATCHLEN]

从以下位置开始可用：: 7.0.0
时间复杂度：: O（N*M），其中 N 和 M 分别是 s1 和 s2 的长度
ACL 类别：: @read, @string, @slow,

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

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

LCS 对于评估两个字符串的相似程度非常有用。字符串可以表示许多事物。例如，如果两个字符串是 DNA 序列，LCS 将提供两个 DNA 序列之间相似性的度量。如果字符串表示某个用户编辑的某些文本，则 LCS 可以表示新文本与旧文本相比的差异程度，依此类推。

请注意，此算法在O(N*M)time，其中 N 是第一个字符串的长度，M 是第二个字符串的长度。因此，要么旋转不同的 Redis 实例来运行此算法，要么确保针对非常小的字符串运行它。

> 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

最后，还要具有匹配项 len：

> 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 时最长的公共子序列的长度。
地图回复：给定 IDX 时，包含 LCS 长度和两个字符串中所有范围的地图。