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)，其中 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 响应
以下之一
RESP3 响应
以下之一