CLR cover
Previous problem

Problem 130: Local periodicity lemma with one don't care symbol

Next problem
\( \def\pgcd{\mathit{gcd}} \)

The problem concerns periodicities occurring inside a word that contains one occurrence of a don't care symbol (also called hole or joker). It is a letter, denoted by $*$, that stands for any other letter of the alphabet, that is, it matches any letter including itself. For a string $x$, two of its letters, $x[i]$ and $x[j]$, are said to $\approx$-match, written $x[i]\approx x[j]$, if they are equal or one of them is the don't care symbol.

Furher, an integer $p$ is a local period of $x$ if for each position $0\leq i\lt |x|-p$, we have $x[i]\approx x[i+p]$. Recall the Periodicity lemma for usual words (see Periodicity).

Lemma 1 (Periodicity lemma)

Let $x$ be a word (without don't care symbol) and let $p,q$ be periods of $x$ that satisfy $p+q-\pgcd(p,q)\leq|x|$. Then $\pgcd(p,q)$ is also a period of $x$.

The problem is related to an extension of this lemma to words in which only one don't care symbol occurs.

(Local periodicity lemma)
Let $x$ be a word with one don't care symbol and $p,q$ be two relatively prime local periods of $x$ and satisfy $p+q\leq|x|$. Then $1$ is also a local period of $x$.

Give example of a word $x$ with one don't care symbol having local periods $p=5$ and $q=7$ with $p+q-1=|x|$ but not having $1$ as local period.

The example in this question shows the inequality in the first question is tight.

References