一、字符串哈希的含义

hash，就是将一个东西映射成另一个东西，类似于Map。 key->value

那么对于字符串Hash，其实就是将构造一个数字使它唯一代表一个字符串，
用它的目的在于比较一个滚动的字符串是否相同的时候，我们不需要重新比较这两个字符串所有的字符，而是直接通过简单的数字计算就可以得出滚动后的字符串所对应的value，从而比较value值判断字符串是否相等，其时间复杂度为O(1)，这是一个极其高效的比较方式

二、例题

2.1 题目

例题

2.2 题目解读

此题查找的是找出最长的重复字串，关键点在于:重复子串部分可以有重叠，因此我们需要逐个对比
即枚举每个下标i然后取模式串的长度k，判断以下标i开始长度为k的字串是否有与其相等的字串

2.3 朴素解法

枚举，然后暴力比较

缺点：比较函数是逐个字符比较，相邻的两个字符串有很多公共部分没有合理利用。时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string longestDupSubstring(string s) {
        int n = s.length() - 1;
        for(int len = n; len > 0; len-- ){
            unordered_set<string>st;
            for(int i = 0; i < s.length() + 1 - len; ++i){
                //cout << s.substr(i,len) << endl;
                if(st.find(s.substr(i,len))!=st.end())
                    return s.substr(i,len);
                st.insert(s.substr(i,len));
            }
            //cout <<endl;
        }
        return "";
    }
};

2.4 字符串哈希解法

· 构造字符串Hash，首先我们将每个字符串的字符都对应成一个数字

· 然后将他们按照顺序乘以Base的幂进行相加

· 由于这数字一般会很大，所以我们需要取余数（MOD）(一个大素数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//由于每次都是固定，长度所以不用h和p的数组
class Solution {
 public:
  using ull = unsigned long long;//超出后自动取模
  const ull b = 131;
  string longestDupSubstring(string s) {
    int l = 0, n = s.length(), r = n - 1, pos = 0;
    auto check = [&](int k) {  //返回的是以i为起始位置长度为k的字串
      ull h = 0, p = 1;
      for (int i = 0; i < k; ++i) {
        h = h * b + s[i];
        p = p * b;
      }
      unordered_set<ull> st{h};
      for (int i = k; i < n; ++i) {
        h = h * b + s[i] -
            p * s[i - k];  //由于h就是长度为k+1的前缀和，只需-p[i-k]
        if (st.count(h)) return i;
        st.insert(h);
      }
      return 0;  //没有找到就返回0
    };
    while (l < r) {
      int m = (l + r + 1) >> 1;
      int ret;
      (ret = check(m)) ? l = m : r = m - 1;
      ret ? pos = ret : pos;
    }  // 最终 l = r;为长度
    cout << l << r <<endl;
    return s.substr(pos - l + 1, l);
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//h和p都用数组存
class Solution {
 public:
  using ull = unsigned long long;//超出后自动取模
  const ull b = 131;
  //前缀数组包含当前i值
  ull h[30005];
  ull p[30005];
  string longestDupSubstring(string s) {
    int l = 0, n = s.length(), r = n - 1, pos = 0;
    h[0] = s[0],p[0] = 1;
    for (int i = 1; i < n; ++i) {
         h[i] = h[i-1] * b + s[i];
         p[i] = p[i-1] * b;
    }
    auto check = [&](int k) {  //返回的是以i为起始位置长度为k的字串
      unordered_set<ull> st{};
      for (int i = 0; i + k - 1 < n ; ++i) {//枚举起始点
         int j = i + k - 1;
         ull temp ; 
         if (i == 0) temp = h[j]; 
         else temp = h[j] - h[i-1] * p[j - i + 1];
         //cur = h[right] - h[left-1] *(p[right - left  + 1] 或者 p [len])
         if (st.count(temp)) return i;//返回数组的结尾的位置(根据return值定义)
         st.insert(temp);
      }
      return 0;  //没有找到就返回0
    };
    while (l < r) {
      int m = (l + r + 1) >> 1;
      int ret;
      (ret = check(m)) ? l = m : r = m - 1;
      ret ? pos = ret : pos;
    }  // 最终 l = r;为长度
    cout << l << r <<endl;
    return s.substr(pos, l);
  }
};