Longest Common Subsequence (LCS)

A Longest Common Subsequence (LCS) is a string [math]\displaystyle{ S_1 }[/math] that is in a subsequence relation with every member of string set [math]\displaystyle{ S }[/math] and with no other string [math]\displaystyle{ (S_2\in S) }[/math] in a subsequence relation with the string set is shorter than [math]\displaystyle{ S_1 }[/math].

• AKA: LCSS, Maximal Common Subsequence.
• Context:
  • It can be discovered by an LCS System (that implements an LCS algorithm to solve an LCS task).
  • ..
• Example(s):
  • [a b c] ⇐ LCS([a s b e t c h d]; [r t w a b g j c k t f]).
  • …
• Counter-Example(s):
  • Shortest Common Subsequence.
  • Shortest Common Supersequence.
  • Shortest Common Superstring.
  • Longest Common Substring(LCG.
• See: Longest Common Supersequence Task, MCS Algorithm, Linear Space Algorithm, ROUGE-L.

---

---

References

2009

• http://www.itl.nist.gov/div897/sqg/dads/HTML/longestCommonSubsequence.html
  • The problem of finding a maximum length (or maximum weight) subsequence of two or more strings.
  • Also known as heaviest common subsequence.
  • NOTES: The longest common substring is contiguous, while the longest common subsequence need not be.

1975

• (Hirschberg, 1975) ⇒ Daniel S. Hirschberg. (1975). “A Linear Space Algorithm for Computing Maximal Common Subsequences.” In: Communications of the ACM, 186).

---