找出最长重复子数组的长度

Question

给定一个 1 到 10^5 之间的整数数组，找到最佳时间和 space 最长重复子数组的长度。我正在考虑进行二进制搜索，但我想听听一些建议。感谢您的帮助！

Answer 1

确实可以使用二分查找，但它需要对数组进行哈希处理才能提高整体算法的效率，您可以阅读有关滚动哈希的更多信息，滚动哈希就像为子数组创建哈希，所以如果您想要要检查两个子数组是否相等，那么您只需在 O(1) 时间内检查它们的滚动哈希，如果它们相等，则它们非常有可能是相等的，具体取决于您的哈希函数，因此您将对 len 进行二进制搜索所需的重复子数组，即假设长度范围是从 0 到 (n/2)，其中 n 是数组的大小，0 表示不存在重复子数组，因此假设我们将中间值作为潜在答案，进行检查现在创建一个散列图的函数，其中整数是键，值是向量，它存储长度为 mid

的子数组的所有起始位置的散列

unordered_map<int , vector<int>>pos;

现在遍历数组并将所有散列存储为键，并将它们的起始位置存储在向量中，因此如果重复两个散列，它将进入同一个向量，现在一旦完成，我们得到了最大 n 个不同的哈希值，所以遍历 map 中的哈希值，如果向量的大小大于 1，则检查对应哈希值的向量的第一个和最后一个元素的 pos 之间的差异，如果差异is >= len(or mid) 那么是的，你有一个长度为 mid 的子数组并将其存储在我们的答案中，这是重复的，现在二分查找的魔力来了，我们可以很容易地证明如果这个 subarray/substring正在重复然后它的任何 subarray/substring 也在重复，所以在这种模式的基础上，我们尝试寻求更高的 len 这可能是潜在的答案，即我们更新 l = mid + 1，现在假设我们得到的 mid 不是有效的 len，因此可以肯定不会存在长度大于或等于此重复的子数组，因此我们选择稍低的范围，即 r = mid - 1，然后执行直到我们完成我们的二进制搜索，它将有最大 log(n/2) 迭代并且每个检查函数将在二进制 se 的每次迭代中有 n 次迭代arch 所以这个算法的总复杂度（假设你正在使用散列并获得 substring/subarray 散列，它可以在 O(1) 中检索，这实际上可以通过首先对原始数组进行一些预处理并制作一个具有散列值的新数组通过它我们可以得到子数组哈希）是 n * log(n/2) => O(n*log(n)) 下面是用于理解的 c++ 粗略代码

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
bool check(vector<int> & a , int len){

    int n = a.size();
    unordered_map<int , vector<int>> pos;

    for(int i = 0; i < n - len + 1; ++i){
        int hash_value = subarray_hash(a , i , i + len - 1); // some function to get subarray hash, which I have not implementated for OP exercise
        pos[hash_value].push_back(i);
    }
    for(auto it = pos.begin(); it != pos.end(); ++it){
        vector<int> all_pos = *it;
        if(all_pos.size() > 1){
            int k = all_pos.size();
            if(all_pos[k - 1] - all_pos[0] >= len){
                return true;
            }
        }
    }
    return false;
}
int main(){

    int n;
    cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    int maxlen_possible = 0;
    int l = 0 , r = (n/2);
    while(l <= r){
        int mid = (l + (r - l)/2);
        if(check(a , mid)){
            maxlen_possible = mid;
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    cout << maxlen_possible << "\n";

return 0;
}

现在计算subarray/substringhash，可以参考网上的rolling hash，有不明白的地方告诉我。

找出最长重复子数组的长度

Find the length of the longest repeated subArray

algorithm

sub-array

array-algorithms