Longest Common Subsequence (LCS) Algorithm

A Longest Common Subsequence (LCS) Algorithm is a search algorithm that can be implemented by an LCS system to solve an LCS task.

• Context:
  • …
• Counter-Examples(s):
  • Longest Common Substring Algorithm.
• See: Dynamic Programming, Common Subgraph Algorithm.

---

---

References

2009

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
  • The LCS problem has what is called an "optimal substructure": the problem can be broken down into smaller, simple "subproblems", which can be broken down into yet simpler subproblems, and so on, until, finally, the solution becomes trivial. The LCS problem also has what are called "overlapping subproblems": the solution to a higher subproblem depends on the solutions to several of the lower subproblems. Problems with these two properties — optimal substructure and overlapping substructure — can be approached by a problem-solving technique called dynamic programming, in which the solution is built up starting with the simplest subproblems. The procedure requires what is called "memoization": saving the solutions to one level of subproblem in a table so that the solutions are available to the next level of subproblems. This method is illustrated here.

2009a

• Anand Rajaraman, and Jeffrey D. Ullman. (2009). “Applications and Variants of LSH." Stanford CS345A, Winter 2009: Data Mining. 2/2

2009b

• Anand Rajaraman, and Jeffrey D. Ullman. (2009). “Distance Measures, Generalizations of Minhashing and LSH." Stanford CS345A, Winter 2009: Data Mining. 2/2-2/4

2003

• Ronald I. Greenberg (2003). “Bounds on the Number of Longest Common Subsequences. v2. http://arxiv.org/abs/cs.DM/0301030.

2000

• L. Bergroth and H. Hakonen, and T. Raita (2000). “A Survey of Longest Common Subsequence Algorithms.” In: IEEE SPIRE 2000 doi:10.1109/SPIRE.2000.878178.

1978

• David Maier. (1978). “The Complexity of Some Problems on Subsequences and Supersequences.” In: Journal of ACM, 25(2). doi:10.1145/322063.322075.

1975

• (Hirshberg, 1975) ⇒ Dan S. Hirschberg. (1975). “A Linear Space Algorithm for Computing Maximal Common Subsequences." Communications of the ACM, 18(6). doi:10.1145/360825.360861.

---