Checking whether a word is Hamming-isometric in linear time
share
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 u differs from v, in such a way that all of the new words obtained in this process also avoid f. Words which are not Hamming-isometric have been characterized as words having a border with two mismatches. We derive from this characterization a linear-time algorithm to check whether a word is Hamming-isometric. It is based on pattern matching algorithms with k mismatches. Lee-isometric words over a four-letter alphabet have been characterized as words having a border with two Lee-errors. We derive from this characterization a linear-time algorithm to check whether a word over an alphabet of size four is Lee-isometric.
READ FULL TEXT