The Max-Shift Algorithm for Approximate String Matching

Research output: Chapter in Book/Report/Conference proceedingConference paper

12 Citations (Scopus)


The approximate string matching problem is to find all locations which a pattern of length m matches a substring of a text of length n with at most k differences. The program agrep is a simple and practical bit-vector algorithm for this problem. We consider the following incremental version of the problem: given an appropriate encoding of a comparison between A and bB, can one compute the answer for A and B, and the answer for A and Bc with equal efficiency, where b and c are additional symbols? Here we present an elegant and very easy to implement bit-vector algorithm for answering these questions that requires only O(n[m/w]) time, where n is the length of A, m is the length of B and w is the number of bits in a machine word. We also present an O(nm[h/w]) algorithm for the fixed-length approximate string matching problem: given a text t, a pattern p and an integer h, compute the optimal alignment of all substrings of p of length h and a substring of t.
Original languageEnglish
Title of host publicationAlgorithm Engineering
Subtitle of host publication5th International Workshop, WAE 2001 Århus, Denmark, August 28–31, 2001 Proceedings
EditorsG.S.Brodal , D.Frigioni , A.Marchetti-Spaccamela
Place of PublicationBerlin and New York
PublisherSpringer Berlin Heidelberg
Number of pages13
ISBN (Print)9783540425007
Publication statusPublished - 2001
EventWAE 2001: 5th International Workshop on Algorithm Engineering - Arhus, Denmark
Duration: 28 Aug 200131 Aug 2001

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


ConferenceWAE 2001: 5th International Workshop on Algorithm Engineering


Dive into the research topics of 'The Max-Shift Algorithm for Approximate String Matching'. Together they form a unique fingerprint.

Cite this