Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Mining Bit-Parallel LCS-length Algorithms
verfasst von : Heikki Hyyrö
Erschienen in: String Processing and Information Retrieval
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Some of the most efficient algorithms for computing the length of a longest common subsequence (LLCS) between two strings are based on so-called “bit-parallelism”. They achieve \(O(\lceil m/w \rceil n)\) time, where m and n are the string lengths and w is the computer word size. The first such algorithm was presented by Allison and Dix [3] and performs 6 bit-vector operations per step. The number of operations per step has later been improved to 5 by Crochemore et al. [5] and to 4 by Hyyrö [6]. In this short paper we explore whether further improvement is possible. We find that under fairly reasonable assumptions, the LLCS problem requires at least 4 bit-vector operations per step. As a byproduct we also present five new 4-operation bit-parallel LLCS algorithms.