Finding approximate palindromes in strings

Details Finding approximate palindromes in strings Finding approximate palindromes in strings

2003-09-23

arxiv.org/abs/cs/0309043v1

Pattern Recognition 35 (2002), 2581-2591

Computer Science

Data Structures and Algorithms

Scientific paper

10.1016/S0031-3203(01)00179-0

We introduce a novel definition of approximate palindromes in strings, and provide an algorithm to find all maximal approximate palindromes in a string with up to $k$ errors. Our definition is based on the usual edit operations of approximate pattern matching, and the algorithm we give, for a string of size $n$ on a fixed alphabet, runs in $O(k^2 n)$ time. We also discuss two implementation-related improvements to the algorithm, and demonstrate their efficacy in practice by means of both experiments and an average-case analysis.

Affiliated with

Also associated with

No associations

Rating

Finding approximate palindromes in strings 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 Finding approximate palindromes in strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding approximate palindromes in strings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-182682