题解 | #最长重复子串 -- 字符串哈希#

字符串哈希

这题与 LeetCode 1044 最长重复子串 类似，
不同的是，这里的子串的首尾相连，那么根据力扣这题的思路，可以计算前后长度为L的[i, i + L - 1]和[i + L, i + 2 * L - 1]的字符串哈希值，然后判断这个哈希值是否相等，如果相等说明，存在；
时间复杂度：，题目要求是C++ 5s，不会超时哈！
空间复杂度：

class Solution {
public:
    typedef unsigned long long ULL;
    const ULL MOD = pow(2, 48);
    bool helper(const string& s, int L){ //返回下标
        int n = s.length();
        ULL secret[2] = {0, 0};
        ULL factor = 1;
        const ULL BASE = 131;
        for(int i = 0; i < L; i ++){
            secret[0] = (((secret[0] % MOD) *  BASE ) % MOD + s[i] - 'a') % MOD;
            secret[1] = (((secret[1] % MOD) *  BASE ) % MOD + s[i + L] - 'a') % MOD;
            if(i > 0) factor = (factor % MOD) * BASE % MOD;
        }
        if(secret[0] == secret[1]) return true;
        for(int i = L; i + L <= n; i ++){
            secret[0] = (secret[0] % MOD - (factor % MOD * (s[i - L] - 'a') % MOD) + MOD) % MOD;
            secret[0] = ((secret[0] % MOD * BASE) % MOD + s[i] - 'a') % MOD;
            secret[1] = (secret[1] % MOD - (factor % MOD * (s[i] - 'a') % MOD) + MOD) % MOD;
            secret[1] = ((secret[1] % MOD * BASE) % MOD + s[i + L] - 'a') % MOD;
            if(secret[0] == secret[1]) return true;
        }
        return false; //不存在重复子串
    }
    int solve(string a) {
        // write code here
        int n = a.length();
        int L = n / 2;
        while(L > 0){
            if(helper(a, L)) return 2 * L;
            L --;
        }
        return 0;
    }
};