Palindromes in circular words
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...
| Main Author: | |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/26621 |
| Summary: | 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/3. For n divisible by 3 we present circular words of length n containing 5n/3 -2 distinct palindromes, so the bound is almost sharp. The paper finishes with some open problems. |
|---|