Article ID Journal Published Year Pages File Type
434110 Theoretical Computer Science 2014 13 Pages PDF
Abstract

There is a very short and beautiful proof that the number of distinct non-empty palindromes in a word of length n is at most n. In this paper we show, with a very complicated proof, that the number of distinct non-empty palindromes with length at most n in a circular word of length n   is less than 5n/35n/3. For n divisible by 3 we present circular words of length n   containing 5n/3−25n/3−2 distinct palindromes, so the bound is almost sharp. The paper finishes with some open problems.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,