Finding approximate palindromes in strings
| dc.creator | Porto, A. H. L. | |
| dc.creator | Barbosa, V. C. | |
| dc.date | 2003-09-23 | |
| dc.date.accessioned | 2026-07-07T07:46:33Z | |
| dc.date.available | 2026-07-07T07:46:33Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0309043 | |
| dc.identifier | http://arxiv.org/abs/cs/0309043 | |
| dc.identifier | Pattern Recognition 35 (2002), 2581-2591 | |
| dc.identifier | doi:10.1016/S0031-3203(01)00179-0 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/123863 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.2; I.2.8 | |
| dc.title | Finding approximate palindromes in strings | |
| dc.type | text |