LCS

Syntax
LCS key1 key2 [LEN] [IDX] [MINMATCHLEN min-match-len] [WITHMATCHLEN]
Available since:
7.0.0
Time complexity:
O(N*M) where N and M are the lengths of s1 and s2, respectively
ACL categories:
@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 reply: 最长公共子序列。
  • Integer reply: 当给定LEN时，最长公共子序列的长度。
  • Array reply: 当给定IDX时，返回一个包含LCS长度和两个字符串中所有范围的数组。

RESP3 回复

以下之一：

  • Bulk string reply: 最长的公共子序列。
  • Integer reply: 当给定LEN时，最长公共子序列的长度。
  • Map reply: 当给定IDX时，返回一个包含LCS长度和两个字符串中所有范围的映射。

RATE THIS PAGE
Back to top ↑