Efficient algorithm to get cyclic Hamming distance

Abstract

In this text we use the cross-correlation method using the fast Fourier transform to present a simple algorithm, with a time complexity of O(N log N), in order to calculate the exact value of the cyclic Hamming distance between two sequences of length N over any alphabet of size k. It may be useful in applications where we only want to know that value, like in sequence alignment, without taking into account insertions and deletions.