LCS

语法
LCS key1 key2 [LEN] [IDX] [MINMATCHLEN min-match-len] [WITHMATCHLEN]
可用版本
Redis 开源版 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)，其中 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

最后，还可以获取匹配长度

> 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 回复：最长公共子序列。
  • Integer 回复：当指定 LEN 时，最长公共子序列的长度。
  • Array 回复：当指定 IDX 时，一个包含 LCS 长度和两个字符串中所有范围的数组。

RESP3 回复

以下之一

  • Bulk string 回复：最长公共子序列。
  • Integer 回复：当指定 LEN 时，最长公共子序列的长度。
  • Map 回复：当指定 IDX 时，一个包含 LCS 长度和两个字符串中所有范围的 map。

评价此页面
返回顶部 ↑