Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The Number of Distinct Subpalindromes in Random Words

Rubinchik M., Shur A. M.

Fundamenta Informaticae

2016

Vol. 145, nr 3

371--384

We prove that a random word of length n over a k-ary fixed alphabet contains, on expectation,Θ(√n) distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit limn→∞ E(n, k)=√n does not exist for any κ ≥ 2, lim infn→∞ E(n; k)=√n =Θ(1), and lim supn→∞ E(n; k)=√n = Θ(√k). Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.