Journal
MATHEMATICS IN COMPUTER SCIENCE
Volume 11, Issue 2, Pages 113-126Publisher
SPRINGER BASEL AG
DOI: 10.1007/s11786-016-0280-2
Keywords
Algorithm design; Algorithms on strings; Pattern matching; String matching; String; Border
Categories
Ask authors/readers for more resources
We consider the problem of on-line exact string matching of a pattern in a set of highly similar sequences. This can be useful in cases where indexing the sequences is not feasible. We present a preliminary study by restricting the problem for a specific case where we adapt the classical Morris-Pratt and Knuth-Morris-Pratt algorithms to consider borders with errors. We give an original algorithm for computing borders at Hamming distance 1. We exhibit experimental results showing that our algorithms are much faster than searching for the pattern in each sequences with a very fast on-line exact string matching algorithm.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available