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 = x1, . . . , xn and Y = y1, . . . , ym For example, X = B, D, C, A, B, A and Y = A, B, C, B, D, A, B.