Suppose we are given a language $\Sigma$ where, suppose, $|\Sigma| = O(1)$. Consider two fixed strings $A, B \in \Sigma^n$. Define the Hamming metric between these strings as $$d_{H}(A,B) = \sum_{i=1}^n \boldsymbol{1}\lbrace A(i) \neq B(i)\rbrace$$ If we define $B^{(k)}$ as the $k$-shift (to the right) cyclic permutation of $B$, then what I am looking to compute is $$d_{\text{cyc},H}(A,B) = \min_{k \in \lbrace 0, \cdots, n-1 \rbrace} d_H\left(A, B^{(k)}\right)$$ So it is easy to see that we can compute $d_H(A,B)$ for some length $n$ strings $A$ and $B$ in time $O(n)$, implying a trivial $O(n^2)$ algorithm for $d_{\text{cyc},H}(A,B)$. So my goal is to see if we can do something better. If someone knows of an algorithm that generalizes to any constant value for $|\Sigma|$, I would be happy to know. For now, I will lay out some of my thoughts.
Suppose that $|\Sigma| = 2$, namely that $\Sigma = \lbrace \alpha, \beta \rbrace$. Let us define a map $h: \Sigma \rightarrow \lbrace -1, 1 \rbrace$ where, say, $h(\alpha) = -1$ and $h(\beta) = 1$. If we transform the strings $A$ and $B$ element-wise to strings $A'$ and $B'$ in $\lbrace -1, 1\rbrace^n$, we can then compute all of the $d_H\left(A, B^{(k)}\right)$ values via a FFT of the concatenated string $B'B'$ and $A'$. We can see this by first considering the computation of $d_H(A,B)$. Suppose $I_{=} \subseteq [n]$ is the set of indices for characters where $A$ and $B$ are the same and make $I_{\neq} = [n] \setminus I_{=}$ the set of indices where $A$ and $B$ differ. Clearly $I_{=}$ and $I_{\neq}$ are disjoint, so $|I_{=}| + |I_{\neq}| = n$. Now let us compute the inner product of $A'$ and $B'$. Any element where $A$ and $B$ have the same character, $A'$ and $B'$ will have the same sign at that element. Any element where $A$ and $B$ differ, the signs will differ as well. Thus we find that $$(A' \cdot B') = \sum_{i=1}^n A'(i) B'(i) = \sum_{i \in I_=} A'(i) B'(i) + \sum_{i \in I_{\neq}} A'(i) B'(i) = |I_=| - |I_{\neq}|$$ As $d_H(A,B) = |I_{\neq}|$ and $(A'\cdot B') = |I_{=}| - |I_{\neq}| = n - 2 |I_{\neq}|$, this implies that we can find $d_H(A,B)$ to be equal to $$d_H(A,B) = |I_{\neq}| = \frac{1}{2}\left(n - (A' \cdot B')\right)$$ Now if $\text{rev}(S)$ reverses a string $S$ of size $n$, implying that $S(i) = \text{rev}(S)(n-i)$, we can observe that if we define the string $C' = \text{rev}(B'B')$, we can find for any $k \in [n]$ that \begin{align} v_k &:= \sum_{i=1}^n C'((n-k+1)-i)A'(i)\\ &= \sum_{i=1}^n (B'B')((k-1) + i)A'(i) \\ &= \sum_{i=1}^n (B')^{(k-1)}(i) A'(i) \\ &= \left((B')^{(k-1)} \cdot A'\right) \\ &= n - 2 d_H\left( A, B^{(k-1)} \right) \end{align}
This implies doing the convolution of the strings $C'$ and $A'$ give us a mechanism to compute all values for $d_H\left(A, B^{(k)}\right)$, which can be done in $O(n \log(n))$ time using the Fast Fourier Transform (FFT). This sounds great for the special case that $|\Sigma| = 2$, but I am unsure about an efficient, exact way that generalizes to larger constant values for the size of $\Sigma$.
My initial thought as an approximation is to create, say, an $r$-wise independently family of hash functions $\mathcal{H} := \left\lbrace h: \Sigma \rightarrow \lbrace -1, 1 \rbrace \,|\, \forall c \in \Sigma, h(c) = 1 \text{ with prob } 1/2\right\rbrace$ for $r$ at least 2, uniformly sample some $h \in \mathcal{H}$, and then for a string $A \in \Sigma^n$ set $A'(i) = h(A(i))$. If we define the random variable $Y(A,B) = A' \cdot B'$ under this type of transformation, we can find that \begin{align} \mathbb{E}\left(Y(A,B)\right) &= \sum_{i=1}^n \mathbb{E}\left(A'(i)B'(i)\right) \\ &= \sum_{i \in I_{=}} \mathbb{E}\left( A'(i)B'(i)\right) + \sum_{i \in I_{\neq}} \mathbb{E}\left(A'(i)B'(i)\right) \end{align} Consider two characters $a, c \in \Sigma$. If $a = c$, then $\mathbb{E}(h(a) h(c)) = \mathbb{E}(h(a)^2) = \mathbb{E}(1) = 1$ since $h(a) = h(c)$. If $a \neq c$, then $\mathbb{E}(h(a) h(c)) = \mathbb{E}(h(a)) \mathbb{E}(h(c)) = 0$. This result implies that \begin{align} \mathbb{E}\left(Y(A,B)\right) &= \sum_{i \in I_{=}} \mathbb{E}\left( A'(i)B'(i)\right) + \sum_{i \in I_{\neq}} \mathbb{E}\left(A'(i)B'(i)\right) \\ &= |I_{=}| \\ &= n - |I_{\neq}| \end{align} Which means that technically we could use the estimator $\hat{d}_H(A,B) = n - Y(A,B)$. Obviously we could then average across $k$ estimates to minimize variance, but at least initial calculations of the variance of this estimator seem to show that the variance satisfies $\text{Var}(\hat{d}_H(A,B)) = \Theta(n^2)$, which kind of makes sense because there are hash functions that could completely get things wrong. Like if we happen to choose a hash function such that $h(c) = 1$ for all $c \in \Sigma$, then we will get an estimate that the strings are identical even if the strings have no overlap, e.g. $A = aaa$ and $B = bbb$. Thus, this randomized approach does not seem sound. If anyone has ideas of how things could be modified to improve the concentration properties, I would be happy to hear them!
Edit 1 I made a separate realization on how to proceed with the randomized approach. We know by Markov's inequality that for some constant $c > 0$ that $$\text{Pr}\left\lbrace \hat{d}_H(A,B) \geq c d_H(A,B)\right\rbrace \leq \frac{\mathbb{E}\left(\hat{d}_H(A,B)\right)}{c d_H(A,B)} = \frac{1}{c}$$ Now suppose we make $m$ iid estimates for $\hat{d}_H(A,B)$ and choose the minimum one as being correct. The only way our minimum estimate will be larger than $c d_H(A,B)$ is if all estimates are larger than this value. Thus, the probability we error is at most $(1/c)^m$. Setting $c = (1 + \epsilon)$ and $m = 2\epsilon^{-1} \ln(1/\delta)$ gives us that with probability at least $1 - \delta$, the minimum of the $m$ estimators is less than $(1 + \epsilon)d_H(A,B)$. Using this fact, we can generate $m$ iid instances for $A'$ and $B'$ in $O(mn)$ time, use them to compute the necessary FFT data in $O(mn \ln(n))$ time to obtains estimates for the each $d_H(A, B^{(k)})$ term across all samples, then compute the minimum of each estimate across all $m$ samples in $O(nm)$ time, and then compute the minimum across these final estimates in $O(n)$ time to obtain the estimate for $d_{cyc,H}(A,B)$.
Putting this all together, setting $\delta = n^{-3}$, we have with probability at least $1 - \frac{1}{n^3}$ that we compute a $(1+\epsilon)$-approximate cyclic string Hamming distance in time $O(\epsilon^{-1} n \text{polylog}(n))$ time when $|\Sigma| = O(1)$.
Note that this is not necessarily great because if we get a bad hash function, we may incorrectly return a cyclic Hamming distance estimate of $0$ because the hash function may think the strings are equivalent. So it would be nice to figure out a way to get an estimate with high probability that is only a small amount less than the true value.
Edit 2 As the above randomized approach was not too good, I went a different approach by considering things from a streaming model type of approach. Suppose we have a stream $S$ where the $i^{th}$ item from the stream is the tuple $(A[i], B[i])$ from the potentially large strings $A$ and $B$. The idea was to use reservoir sampling to get a $k$-sample of these tokens, form them into strings $A_k$ and $B_k$, and then computing the estimate of the cyclic Hamming distance of strings $A$ and $B$ by doing $$\hat{d}_{\text{cyc},H}\left(A,B\right) = \frac{n}{k} d_{\text{cyc},H}(A_k, B_k)$$
My analysis showed that for $0 < \alpha < 1$ that using this approach, we can get a $O(n^{\alpha})$-approximation with probability at least $1 - 1/n^{O(1)}$where the runtime serially is $O\left((n + n^{1-2\alpha} \ln(n))\ln(n)\right)$ and the space requirements are $O\left(n^{1-2\alpha}\ln(n)\ln|\Sigma|\right)$ bits.
