Combinatorics on partial word borders (Q897922)

A partial word contains holes that can be filled with any character of the alphabet, a border is a non-empty proper prefix that is also a suffix, and the border array contains the length of the longest border of each prefix of the word. The authors determine the maximal number of holes with specified longest border, in particular in an unbordered partial word. They also compute the number of partial words with given border array and describe the sets of possible hole positions in such words. Finally, they count the number of partial words with specified border lengths (or arrays), and they count the number of border arrays. These formulas involve the Bell numbers and the Stirling numbers of the second kind. The main tools are certain graphs: constraint graph, compatibility graph, incompatibility graph, etc. In Theorem 3.3, the formula for \(\mathrm{HSB}_k(2\ell)\) can be simplified to \(2\ell - \lceil 2 \sqrt{\ell} \rceil\).