Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434110 | Theoretical Computer Science | 2014 | 13 Pages |
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
Jamie Simpson,