我正在寻找一个更快的算法，解决以下问题：

• 输入：[0, N)范围内的两个整数数组A和B，长度都是固定的d，假定按排序顺序给出，没有重复的元素。
• 输出：A和B的循环移位之间的最大可能交集（即公共元素的数量）是否大于某个指定的阈值t。

如果有必要的话，我会在Rust中实现它（尽管我对一般算法的改进比特定语言的优化更感兴趣），实际上，t将小于10，d通常在15到150的范围内，N将大致与2*d*d相当。
我目前的算法基本上如下所示（注意，d和N是在编译时定义的常量）：

fn max_shifted_overlap_geq(A: [u32; d], B: [u32; d], threshold: u32) -> bool {
    for i in 0..d {
        for j in 0..d {
            let s = N + A[i] - B[j];
            let mut B_s = [0; d];
            for k in 0..d {
                B_s[k] = (B[k] + s) % N;
            }
            B_s.sort();
            // Actually, I do an insertion-sort in place as I construct B_s,
            // but I'm writing it this way here for simplicity.
            if sorted_intersection_count(&A, &B_s) >= threshold {
                return true;
            }
        }
    }
    false
}

因此，我只是从A[i] - B[j]的可能值中选择移位（因为不是这种形式的移位会产生零交集），然后我只是构造B的循环移位，并以一种相当简单的方式计算共有元素的数量。
有没有一种更有效的算法来解决这个问题，同时考虑到数组的大小相当小？特别是，有没有一种更好的方法来找到更有可能产生大重叠的移位？
编辑：为了提供额外的背景（如下文所要求），这在QC-MDPC代码研究中出现：这些数组表示生成奇偶校验矩阵的循环块的二进制向量的支持，而这个与循环移位相交的条件定义了一类具有某种密码学含义的“弱密钥”（我最初没有提到这一点，因为这个问题在孤立的情况下似乎很有趣，而且不需要任何编码理论或密码学知识）。
编辑2：修正了代码中的一些错别字，并改用了一种更好的方法来计算排序列表的交集（奇怪的是，我在早期版本中实际上使用了这种改进的算法，代码运行得更慢，但这可能是由于实现中的bug或代码中其他地方现在已经修复的问题。
编辑三：为了给以后遇到类似问题的人提供参考，这里是我目前的实现，使用了virchau 13的关键思想，再加上一些小的额外优化。（为了清楚起见，我重命名了一些变量--arr1和arr2表示输入数组，LEN代替d表示数组长度。）

fn relative_shifts(arr1: &[u32; LEN], arr2: &[u32; LEN]) -> [[u32; LEN]; LEN] {
    let n = N as u32;
    let mut shifts = [[0; LEN]; LEN];
    for i in 0..LEN {
        for j in 0..LEN {
            shifts[i][j] = if arr1[i] < arr2[j] {
                n + arr1[i] - arr2[j]
            } else {
                arr1[i] - arr2[j]
            }; // this equals (arr1[i] - arr2[j]) % n
        }
    }
    shifts
}
fn max_shifted_overlap_geq(arr1: &[u32; LEN], arr2: &[u32; LEN], threshold: u8) -> bool {
    let shifts = relative_shifts(arr1, arr2);
    let mut shift_counts = [0; N];
    for i in 0..LEN {
        for j in 0..LEN {
            let count = &mut shift_counts[shifts[i][j] as usize];
            *count += 1;
            if *count >= threshold {
                return true;
            }
        }
    }
    false
}

以下是一些实施注意事项：
1.这可以容易地被修改以产生最大可能的交集作为值（通过在超过阈值时取最大值而不是短路）或索引对的集合（还通过在计算每个移位s时将索引对(i, j)附加到与每个移位s关联的列表）。
1.我们不需要假设数组是排序的，也不需要假设数组的长度是一样的，虽然我还没有对不同长度的数组做过测试.