文件名称：Experimenting an Approximation Algorithm
文件大小：158KB
文件格式：PDF
更新时间：2011-11-07 08:24:14
LCS 最长公共字串
The problem of nding the longest common subsequence (lcs) of a given set of se- quences over an alphabet occurs in many interesting contexts, such as data com- pression and molecular biology, in order to measure the \similarity degree" among biological sequences. Since the problem is NP-complete in its decision version (i.e. does there exist a lcs of length at least k, for a given k?) even over xed alpha- bet, polynomial algorithms which give approximate solutions have been proposed. Among them, Long Run (LR) is the only one with guaranteed constant performance ratio.