Quadratic-time algorithm for a string constrained LCS problem

作     者：Deorowicz, Sebastian 

作者机构：Silesian Tech Univ Inst Informat Gliwice Poland 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2012年第112卷第11期

页      面：423-426页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Algorithms Sequence similarity Longest common subsequence Constrained longest common subsequence 

摘      要：The problem of finding a longest common subsequence of two main sequences with some constraint that must be a substring of the result (STR-IC-LCS) was formulated recently. It is a variant of the constrained longest common subsequence problem. As the known algorithms for the STR-IC-LCS problem are cubic-time, the presented quadratic-time algorithm is significantly faster. (C) 2012 Elsevier B.V. All rights reserved.