TY - CHAP

T1 - The Max-Shift Algorithm for Approximate String Matching

AU - Iliopoulos, Costas S.

AU - Mouchard, Laurent

AU - Pinzon, Yoan J.

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78650726931&partnerID=8YFLogxK

U2 - 10.1007/3-540-44688-5_2

DO - 10.1007/3-540-44688-5_2

M3 - Conference paper

SN - 9783540425007

VL - N/A

T3 - Lecture Notes in Computer Science

SP - 13

EP - 25

BT - Algorithm Engineering

A2 - null, G.S.Brodal

A2 - null, D.Frigioni

A2 - null, A.Marchetti-Spaccamela

PB - Springer Berlin Heidelberg

CY - Berlin and New York

T2 - WAE 2001: 5th International Workshop on Algorithm Engineering

Y2 - 28 August 2001 through 31 August 2001

ER -