LCS(3valkey)

📦
version 9.0.6 · 2 versions
, in fedora 44

💖 LCS — the longest-common-substring bestie 💖

okay so we're in the Valkey Command Manual and today's main character is lcs, which is short for longest common subsequence. she finds the longest common substring between two keys. slay.

✨ SYNOPSIS ✨

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

🌸 DESCRIPTION 🌸

So LCS runs the longest common subsequence algorithm. and no, bestie, that is not the same thing as the longest common string algorithm — because with a subsequence, the matching characters do not need to be contiguous. like at all. they can be scattered, we don't gatekeep. 💅

for example: the LCS between “foo” and “fao” is “fo”, because if you scan both strings left to right, the longest common set of characters is made up of the first “f” and then the “o”. iconic behavior honestly.

LCS is super useful for figuring out how similar two strings are. and strings can be literally anything:

  • if two strings are DNA sequences, LCS gives you a measure of similarity between the two DNA sequences 🧬
  • if the strings are text some user edited, LCS can tell you how different the new text is from the old one
  • and so forth, the possibilities are endless fr fr
⚠️ okay important heads up: this algorithm runs in O(N*M) time, where N is the length of the first string and M is the length of the second string. so either spin up a different Valkey instance to run this, or just make absolutely sure you're running it against very small strings. do not come for me if you pass it a whole novel. 😭
> MSET key1 ohmytext key2 mynewtext
OK
> LCS key1 key2
"mytext"

sometimes you only need the length of the match, and that's valid:

> LCS key1 key2 LEN
(integer) 6

but what's often very very useful is knowing the match position in each of the strings:

> 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

now listen, matches get produced from the last one to the first one, because that's just how the algorithm works and it's more efficient to emit things in that same order. so the array above means: the first match (that's the second element of the array) is between positions 2-3 of the first string and 0-1 of the second. then there's another match between 4-7 and 5-8. the way that the ranges line up?? obsessed.

want to restrict the list of matches to only the ones of a given minimal length? say less:

> 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

and finally, to also have the match 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

periodt. 💖

🦋 REPLY 🦋

RESP2

one of the following, bestie:

  • valkey-protocol(7) Bulk string reply: the longest common subsequence.
  • valkey-protocol(7) Integer reply: the length of the longest common subsequence when LEN is given.
  • valkey-protocol(7) Array reply: an array with the LCS length and all the ranges in both the strings when IDX is given.

RESP3

one of the following, yes it's basically the same list but the last one hits different:

  • valkey-protocol(7) Bulk string reply: the longest common subsequence.
  • valkey-protocol(7) Integer reply: the length of the longest common subsequence when LEN is given.
  • valkey-protocol(7) Map reply: a map with the LCS length and all the ranges in both the strings when IDX is given.

👑 COMPLEXITY 👑

O(N*M) where N and M are the lengths of s1 and s2, respectively

🌈 ACL CATEGORIES 🌈

@read @slow @string

🎀 HISTORY 🎀

  • Available since: 7.0.0

🫶 SEE ALSO 🫶

and that's the whole page babes 💖 this one's from 9.0.0, dated 2025-10-21, and it's giving longest common subsequence excellence. go forth and match some strings, but keep them small fr. ✨🦋🌸

📦 where this page comes from