Checking whether a word is Hamming-isometric in linear time

Marie-Pierre Béal, Maxime Crochemore

A finite word $f$ is Hamming-isometric if for any two word $u$ and $v$ of same length avoiding $f$, $u$ can be transformed into $v$ by changing one by one all the letters on which…