CLR cover

Additional Problem 5: Local Periodicity Lemma with One Don't Care Symbol (Preliminary version)

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

Letter $*$ is called a don't care (hole, joker) and stands for any other letter of the alphabet. It matches any letter including itself. For a string $x$ we write $x[i]\approx x[j]$ if the letters $x[i]$ and $x[j]$ are equal or one of them is the don't care symbol.

An integer $p$ is a local period of $x$ if for each $i\lt |x|-p$ we have $x[i]\approx x[i+p]$. In Periodicity we presented the periodicity lemma.

Lemma 1 (Periodicity lemma)

If $p$ and $q$ are periods of a word $x$ and satisfy $p+q-\pgcd(p,q)\leq|x|$ then $\pgcd(p,q)$ is also a period of $x$.

Our question is related to an extension of this lemma to words with one don't care symbol. For simplicity we assume $p,q$ are relatively prime.

Show the following local periodicity lemma.
Assume $p,q$ are relatively prime and $x$ is a word with one don't care symbol. Show that if $p$ and $q$ are local periods of $x$ and satisfy $p+q\leq|x|$ then $1$ is also a local period of $x$.

Use the periodicity lemma for standard words.

For $p=5,q=7$ give example of a word $x$ having local periods $p,q$, with one don't care, such that $|x|=p+q-1$, and $x$ has no local period $1$.

References