Faster Approximate String Matching for Short Patterns

Details Faster Approximate String Matching for Short Patterns Faster Approximate String Matching for Short Patterns

2008-11-21

arxiv.org/abs/0811.3490v2

Computer Science

Data Structures and Algorithms

To appear in Theory of Computing Systems

Scientific paper

We study the classical approximate string matching problem, that is, given strings $P$ and $Q$ and an error threshold $k$, find all ending positions of substrings of $Q$ whose edit distance to $P$ is at most $k$. Let $P$ and $Q$ have lengths $m$ and $n$, respectively. On a standard unit-cost word RAM with word size $w \geq \log n$ we present an algorithm using time $$ O(nk \cdot \min(\frac{\log^2 m}{\log n},\frac{\log^2 m\log w}{w}) + n) $$ When $P$ is short, namely, $m = 2^{o(\sqrt{\log n})}$ or $m = 2^{o(\sqrt{w/\log w})}$ this improves the previously best known time bounds for the problem. The result is achieved using a novel implementation of the Landau-Vishkin algorithm based on tabulation and word-level parallelism.

Affiliated with

Also associated with

No associations

Rating

Faster Approximate String Matching for Short Patterns does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster Approximate String Matching for Short Patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Approximate String Matching for Short Patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163117