Landau-Vishkin k-mismatch string matching

Lloyd Allison lloyd at
Wed Aug 25 19:42:08 EST 1993

>In article <anatoly.746231415 at beagle> anatoly at boulder.Colorado.EDU (Ulyanov Anatoly) writes:
>>>Has anyone knowledge of an implementaion of Landau-Vishkin Approximate
>>>string matching.
>>>I have the understanding that the Landau-Vishkin algortihm represent
>>>the state of the art ?

I came across this yesterday, it might be the new state of the art? :

%A J. Tarhio
%A E. Ukkonen
%T Approximate Boyer-Moore string matching.
%J SIAM J. Comput.
%V 22
%N 2
%P 243-260
%D 1993
%K SJC, match, search, k-mismatch, mismatch, change, substitution,
   indel, insert, delete, Boyer Moore
%X |pattern|=m, |text|=n, <=k mismatches, |alphabet|=c
   give O(kn(1/(m-k)+(k/c))) algorithm,
   and a related algorithm for <=k differences (indel and/or change).
   Claim fast in practice.

Department of Computer Science,   email: lloyd at
Monash University, Clayton,       Tel:   61 3 565 5205
VICTORIA 3168, AUSTRALIA          Fax:   61 3 565 5146

More information about the Bio-soft mailing list