语法

1
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)$，其中 N 是第一个字符串的长度，M 是第二个字符串的长度。因此，要么启动一个不同的 Redis 实例来运行这个命令，要么确保针对非常小的字符串运行它。

1
2
3
4
5
redis> MSET key1 ohmytext key2 mynewtext
OK
redis> LCS key1 key2
"mytext"
redis>

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

1
2
3
redis> LCS key1 key2 LEN
(integer) 6
redis>

但通常更有用的是知道每个字符串中的匹配位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
redis> 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
redis>

此算法是从后向前生成匹配项的，因为它的工作方式就是这样，并且按相同顺序生成可以提高效率。上面的数组意味着第一个匹配项（数组的第二个元素）是在第一个字符串的 2-3 位置和第二个字符串的 0-1 位置之间。然后在 4-7 和 5-8 位置之间是另一个匹配项。

通过 MINMATCHLEN 设置最小匹配长度，过滤掉小于此长度的匹配项，如以下示例代码设置了最小匹配长度为 4，所以只会输出长度大于等于 4 的匹配项：

1
2
3
4
5
6
7
8
redis> 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

通过 WITHMATCHLEN 不但输出匹配项，还输出每个匹配项的具体长度：

1
2
3
4
5
6
7
8
9
redis> 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

返回值

  • 没有修饰符时，返回最长公共字符集的字符串表示。
  • 当使用 LEN 修饰符时，返回最长公共字符集的长度。
  • 当使用 IDX 修饰符时，返回一个数组，包括最长公共字符集的长度以及两个字符串中所有匹配项的范围（每个字符串的起始和结束偏移量）。当同时使用 WITHMATCHLEN 修饰符时，表示每个匹配项的数组还将包含该匹配项的长度。

（END）