CLR cover
Previous problem

Problem 8: Distinct Periodic Words

Next problem

In this problem we examine how much different two periodic words of the same length can be. The difference is measured with the Hamming distance. The Hamming distance between $x$ and $y$ of the same length is $\HAM(x,y)=|\{j \mid x[j]\neq y[j]\}|$.

We consider a word $x$ whose period is $p$, a word $y$ of length $|x|$ whose period $q$ satisfies $q\leq p$ and we assume there is at least a mismatch between them. Let $i$ be the position on $x$ and on $y$ of a mismatch, say, $x[i]=\sa{a}$ and $y[i]=\sa{b}$. In the picture $x=u^2$, $|u|=p$, and $|v|=q$.

Distinct Periodic Words

What is the minimal Hamming distance between two distinct periodic words of the same length?
Consider different cases of position $i$ according to periods $p$ and $q$.

References

  • M. Alzamel, M. Crochemore, C. S. Iliopoulos, T. Kociumaka, R. Kundu, J. Radoszewski, W. Rytter, and T. Walen. How much different are two words with different shortest periods. In L. S. Iliadis, I. Maglogiannis, and V. P. Plagianakos, editors, Artificial Intelligence Applications and Innovations - AIAI 2018 IFIP WG 12.5 International Workshops, SEDSEAL, 5G-PINE, MHDW, and HEALTHIOT, Rhodes, Greece, May 25-27, 2018, Proceedings, volume 520 of IFIP Advances in Information and Communication Technology, pages 168-178. Springer, 2018.
  • A. Amir, C. S. Iliopoulos, and J. Radoszewski. Two strings at Hamming distance 1 cannot be both quasiperiodic. Inf. Process. Lett., 128:54-57, 2017.