2002 | OriginalPaper | Buchkapitel
On Maximal Suffices and Constant-Space Linear-Time Versions of KMP Algorithm
verfasst von : Wojciech Rytter
Erschienen in: LATIN 2002: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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
We investigate several simple ways of transforming Knuth- Morris-Pratt algorithm (KMP) into a constant-space and still linear time string-matching algorithm. We also identify a class of very special patterns for which the transformation is particularly simple and show usefulness of the class. Constant-space linear-time string-matching algorithms are usually very sophisticated. Most of them consist of two phases: (very technical) preprocessing phase and searching phase. An exception is onephase Crochemore’s algorithm [2]. It is an on-line version of KMP algorithm with “on-the-fly” computation of pattern shifts (as approximate periods). We explore further Crochemore’s approach, and construct alternative algorithms which are differently structured. In Crochemore’s algorithm the approximate-period function is restarted from inside, which means that several internal variables of this function are changing globally, also Crochemore’s algorithm strongly depends on the concrete implementation of approximate-periods computation. We present a simple modification of KMP algorithm which works in O(1)-space, O(n)-time for any function which computes periods or approximate periods in O(1)- space, and linear time. The approximate-period function can be treated as a black box. We show also that lexicographically self-maximal patterns are especially well suited for Crochemore-style string matching. A new O(1) space string-matching algorithm, MaxSuffix-Matching, is proposed in the paper, which gives yet another example of applicability of maximal suffices.