×

zbMATH — the first resource for mathematics

Finding approximate palindromes in strings. (English) Zbl 1006.68910
Summary: 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^2n)\) 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.

MSC:
68U99 Computing methodologies and applications
68T10 Pattern recognition, speech recognition
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Knuth, D.E.; Morris, J.H.; Pratt, V.R., Fast pattern matching in strings, SIAM J. comput., 6, 322-350, (1977) · Zbl 0372.68005
[2] Manacher, G., A new linear-time on-line algorithm for finding the smallest initial palindrome of a string, J. ACM, 22, 346-351, (1975) · Zbl 0305.68027
[3] A. Apostolico, D. Breslauer, Z. Galil, Optimal parallel algorithms for periods, palindromes and squares, Proceedings of the International Colloquium on Automata, Languages, and Programming, 1992, pp. 296-307.
[4] Apostolico, A.; Breslauer, D.; Galil, Z., Parallel detection of all palindromes in a string, Theoret. comput. sci., 141, 163-173, (1995) · Zbl 0873.68039
[5] Breslauer, D.; Galil, Z., Finding all periods and initial palindromes of a string in parallel, Algorithmica, 14, 355-366, (1995) · Zbl 0833.68053
[6] Galil, Z., Optimal parallel algorithms for string matching, Inf. control, 67, 144-157, (1985) · Zbl 0588.68022
[7] Gusfield, D., Algorithms on strings, trees, and sequences: computer science and computational biology, (1997), Cambridge University Press New York · Zbl 0934.68103
[8] Jurka, J., Origin and evolution of alu repetitive elements, (), 25-41
[9] Levenstein, V.I., Binary codes capable of correcting insertions and reversals, Sov. phys. dokl., 10, 707-710, (1966)
[10] Sankoff, D.; Kruskal (Eds.), J., Time warps, string edits, and macromolecules: the theory and practice of sequence comparison, (1983), Addison-Wesley Reading, MA
[11] G.M. Landau, U. Vishkin, Introducing efficient parallelism into approximate string matching and a new serial algorithm, Proceedings of the Annual ACM Symposium on Theory of Computing, 1986, pp. 220-230.
[12] Landau, G.M.; Vishkin, U., Fast parallel and serial approximate string matching, J. algorithms, 10, 157-169, (1989) · Zbl 0685.68033
[13] Myers, E.W., An O(nd) difference algorithm and its variations, Algorithmica, 1, 251-266, (1986) · Zbl 0639.68054
[14] Ukkonen, E., Algorithms for approximate string matching, Inform. control, 64, 100-118, (1985) · Zbl 0575.68090
[15] Baeza-Yates, R.; Navarro, G., Faster approximate string matching, Algorithmica, 23, 127-158, (1999) · Zbl 0913.68050
[16] W.I. Chang, J. Lampe, Theoretical and empirical comparisons of approximate string matching algorithms. Proceedings of the Symposium on Combinatorial Pattern Matching, 1992, pp. 175-184.
[17] R. Cole, R. Hariharan, Approximate string matching: a simpler faster algorithm, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 463-472. · Zbl 0942.68033
[18] Stephen, G.A., String searching algorithms, (1994), World Scientific Singapore · Zbl 0831.68028
[19] Ukkonen, E., Finding approximate patterns in strings, J. algorithms, 6, 132-137, (1985) · Zbl 0566.68072
[20] Wu, S.; Manber, U., Fast text searching allowing errors, Commun. ACM, 35, 83-91, (1992)
[21] Landau, G.M.; Vishkin, U., Efficient string matching with k mismatches, Theoret. comput. sci., 43, 239-249, (1986) · Zbl 0597.68055
[22] A.H.L. Porto, Detecting Approximate Palindromes in Strings, M.Sc. Thesis, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil, 1999 (in Portuguese).
[23] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), North-Holland New York · Zbl 1134.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.