Speeding-up Hirschberg and Hunt-Szymanski LCS Algorithms

Issue title: Computing Patterns in Strings

Article type: Research Article

Authors: Crochemore, Maxime | Iliopoulous, Costas S. | Pinzon, Yoan J.

Affiliations: Institut Gaspard-Monge, Université de Marne-la-Vallée, F-77454 Marne-la-Vallée CEDEX 2, France | Department of Computer Science, King's College London, London WC2R 2LS, UK

Abstract: Two algorithms are presented that solve the problem of recovering the longest common subsequence of two strings. The first algorithm is an improvement of Hirschberg's divide-and-conquer algorithm. The second algorithm is an improvement of Hunt-Szymanski algorithm based on an efficient computation of all dominant match points. These two algorithms use bit-vector operations and are shown to work very efficiently in practice.

Keywords: Longest Common Subsequence, bit-parallelism

Journal: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 89-103, 2003