Bit-Parallel Algorithm for the Constrained Longest Common Subsequence Problem

Article type: Research Article

Authors: Deorowicz, Sebastian

Affiliations: Institute of Informatics, Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland. E-mail: sebastian.deorowicz@polsl.pl

Abstract: The problem of finding a constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. Its goal is to find a longest subsequence C of A and B such that P is a subsequence of C. Most of the algorithms solving the CLCS problem are based on dynamic programming. Bit-parallelism is a technique of using single bits in a machine word for concurrent computation. We propose the first bit-parallel algorithm computing a CLCS and/or its length which outperforms the other known algorithms in terms of speed.

Keywords: constrained longest common subsequence, longest common subsequence, dynamic programming, bit-parallel algorithm

DOI: 10.3233/FI-2010-256

Journal: Fundamenta Informaticae, vol. 99, no. 4, pp. 409-433, 2010