Palindromes in circular words
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Glen, A.; Simpson, Jamie (2013)A run in a word is a periodic factor whose length is at least twice its period and which cannot be extended to the left or right (by a letter) to a factor with greater period. In recent years a great deal of work has been ...
Barton, C.; Iliopoulos, Costas; Pissis, S. (2014)Background: Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist ...
Kong, Paul Y.L. (1993)Key words: End zone, prestress transfer, wire tendon, transmission length, pull-in, plain wire, indented wire, concrete strength, size of wire, gradual release, sudden release, shock release, time dependent effects.An ...