算法基础课第二章哈希表

字符串哈希

传送门

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

力扣题目

1044. 最长重复子串 - 力扣（LeetCode）

class Solution {
    static const int N = 4e4;
public:
    typedef unsigned long long ull;
    ull h[N], p[N];
    int start;
    int n;
    int P = 131;
    ull get_hash(int l, int r)
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    string longestDupSubstring(string s) {
        //很容易想到的思路是求解每段区间的最长前后缀
        //但是kmp算只能求开头到任意位置的next，解决这个问题是n^2的复杂度
        //看到数据范围很容易想到二分，当时只想怎么用kmp实现了，忘了字符串匹配的另一种方式，hashstring
        n = s.size();
        p[0] = 1;
        for(int i = 1; i <= n; i ++ )
        {
            h[i] = h[i - 1] * P + s[i - 1];
            p[i] = p[i - 1] * P;
        }
        int l = 0, r = N;
        string res;
        while(l <= r)//二分长度，复杂度为nlogn
        {
            int mid = (l + r) / 2;
            if(check(mid))
            {
                l = mid + 1;
                res = s.substr(start - 1, mid);
            }
            else r = mid - 1;
        }
        return res;
    }
    bool check(int len)
    {
        unordered_map<ull, bool> mp;//记录出现过的字符串，若有相同长度相同值得字符串，那么就是重复子串
        for(int i = 1; i + len - 1 <= n; i ++ )
        {
            ull cnt = get_hash(i, i + len - 1);
            if(mp[cnt])
            {
                start = i;
                return true;
            }
            mp[cnt] = true;
        }
        return false;
    }
};

686. 重复叠加字符串匹配 - 力扣（LeetCode）

class Solution {
public:
    typedef unsigned long long ull;
    ull P = 131;
    string s;
    ull h[40010], p[40010];
    ull get(int l, int r)
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    int repeatedStringMatch(string a, string b) {
        string s;
        int res = 0;
        int n = a.size(), m = b.size();
        while(s.size() < b.size())
        {
            s.append(a);
            res ++;
        }
        s.append(a);
        s.append(b);
        int len = s.size();
        cout << len;
        p[0] = 1;
        for(int i = 1; i <= len; i ++ )
        {
            h[i] = h[i - 1] * P + s[i - 1];
            p[i] = p[i - 1] * P;
        }
        int index = -1;
        ull target = get(len - m + 1, len);
        for(int i = 1; i + m - 1 <= len - m; i ++ )
        {
            if(target == get(i, i + m - 1))
            {
                index = i;
                break;
            }
        }
        if(index == -1) return -1;
        return index <= len - m - n - m + 1 ? res : res + 1;
    }
};