There is a big demand for algorithms that find patterns in strings, for example, DNA. The following optimization problem is called the *longest common subsequence* (LCS).

**Longest Common Subsequence:**

**Instances:** An instance consists of two sequences *X* = *x*_{1}, . . . , *x*_{n} and *Y* = *y*_{1}, . . . , *y*_{m} For example, *X* = *B*, *D*, *C*, *A*, *B*, *A* and *Y* = *A*, *B*, *C*, *B*, *D*, *A*, *B*.

**Solutions: ...**

Start Free Trial

No credit card required