2002/09/17 by A. H. L. Porto, Alexandre H.L. Porto, Valmir C. Barbosa +1
Computer Science · #Algorithms and Data Compression #Machine Learning and Algorithms #cs.DS #semigroups and automata theory
paper · pdf · doi:10.1016/s0031-3203(01)00179-0
published as Pattern Recognition 35 (2002), 2581-2591
openalex publication_date 2002/09/17 · arxiv created 2003/09/23 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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(k2 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.