A Survey of the Longest Common Subsequence Problem and Its Related Problems

by Chen, Jian-bein

ABSTRACT The longest common subsequence (LCS) problem is a classical problem both in com- binational optimization and computational biology. During the past few decades, a considerable number of studies have been focused on LCS and its related prob- lems. In this thesis, we shall present a complete survey on LCS and its related problems, and review some e¡Ócient algorithms for solving these problems. We shall also give the de¡Ânition to each problem, present some theorems, and illustrate time complexity and space complexity of the algorithms for solving these problems.