[LeetCode] 2156. Find Substring With Given Hash Value

• 難度分: 2063

• 這題是 rolling hash，同樣樣到 sliding window 的概念，由左至右需要處理除法問題，會使問題的難度增加，所以這題逆其道而行，從右至左，那就可以把除法問題變成乘法問題了。

• 在處理商數時，要小心處理負數，由於商數 d 必定介於 0~k之間，可以利用

  $$\boxed{\mod(\mod(a)-\mod(b)+k)}$$
  • 證明： $$\boxed{ \begin{array}{ll} 0\le\mod(a)<k \\\\ 0\le\mod(b)<k \\\\ -k<\mod(a)-\mod(b)<k & 在取 \mod 前先整理成正數\\\\ 0<\mod(a)-\mod(b)+k< 2k \\\\ 0<\mod(\mod(a)-\mod(b)+k) < k \end{array} }$$

  令 str = dcba，k = 3，已知 curr = mod(ap^2+bp+c, m) 求 mod(bp^2+cp+d, m)

  • \(\mod(bp^2+cp+d)\)
  • \(\quad = \mod((ap^2+bp+c)\times p +d-ax^3)\)
  • \(\quad = \mod(\mod(ap^2+bp+c)\times p +d+m-\mod(ax^3))\)
  • \(\quad = \mod(\text{curr}\times p +d+m-\mod(ax^3))\)

class Solution {
public:
    string subStrHash(string s, int p, int mod, int k, int val) {
        int n = s.size();
        long pk = 1, curr = 0;
        for (int i = 0; i < k; i++) {
            curr = (curr * p + (s[n-1-i]-'a'+1)) % mod;
            pk = (pk * p) % mod;
        }
        int j = n-k;
        for (int i = k; i < n; i++) {
            curr = (curr * p + (s[n-1-i]-'a'+1) + mod - ((s[n-1-i+k]-'a'+1) * pk) % mod) % mod;
            if (curr == val) j = n-1-i;
        }
        return s.substr(j, k);
    }
};