Efficient Computation of Maximal Anti-Exponent in Palindrome-Free Strings

Article English OPEN
Badkobeh, Golnaz; Crochemore, Maxime; Mohamed, Manal; Toopsuwan, Chalita;
  • Publisher: Elsevier
  • Subject:
    arxiv: Computer Science::Formal Languages and Automata Theory

A palindrome is a string x = a1 · · · an which is equal to its reversal x = an · · · a1. We consider gapped palindromes which are strings of the form uvu , where u, v are strings, |v| ≥ 2, and u is the reversal of u. Replicating the standard notion of string exponent, w... View more
  • References (21)
    21 references, page 1 of 3

    1. G. Badkobeh and M. Crochemore. Computing maximal-exponent factors in an overlap-free string. Journal of Computer and System Sciences, 82(477-487), 2016.

    2. G. Badkobeh, M. Crochemore, and C. Toopsuwan. Maximal anti-exponent of gapped palindromes. In Proceedings of the International Conference on Digital Information and Communication Technology and its Applicationsm DICTAP, pages 205-210, 2014.

    3. S. Chairungsee and M. Crochemore. Efficient computing of longest previous reverse factors. In Y. Shoukourian, editor, Procedddings of the International Conference on Computer Science and Information Technologies CSIT, pages 27-30, Yerevan, 2009. The National Academy of Sciences of Armenia Publishers.

    4. M. Crochemore. Recherche lin´eaire d'un carr´e dans un mot. C. R. Acad. Sc. Paris S´er. I Math., 296(18):781-784, 1983.

    5. M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings, chapter 6.6. Cambridge University Press, 2007. 392 pages.

    6. M. Crochemore and W. Rytter. Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays. Theoretical Computer Science, 88(1):59 - 82, 1991.

    7. M. Crochemore and W. Rytter. Text Algorithms, chapter 8.1 Searching for symmetric words, pages 111-114. Oxford University Press, 1994.

    8. J. D. Currie and N. Rampersad. A proof of Dejean's conjecture. Mathematics of Computation, 80(274):1063-1070, 2011.

    9. F. Dejean. Sur un th´eor`eme de Thue. Journal of Combinatorial Theory, Series A, 13(1):90-99, 1972.

    10. Z. Galil. Real-time algorithms for string-matching and palindrome recognition. In Proceedings of the Annual ACM Symposium on Theory of Computing, pages 161-173, 1976.

  • Related Organizations (8)
  • Metrics
Share - Bookmark