• 難度分: 2063

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

  • 在處理商數時，要小心處理負數，由於商數 d 必定介於 0~k之間，可以利用 mod  (mod  (a)−mod  (b)+k) \boxed{\mod(\mod(a)-\mod(b)+k)}

    • 證明： 0≤mod  (a)<k0≤mod  (b)<k−k<mod  (a)−mod  (b)<k在取mod  前先整理成正數0<mod  (a)−mod  (b)+k<2k0<mod  (mod  (a)−mod  (b)+k)<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  (bp2+cp+d)\mod(bp^2+cp+d)
    • =mod  ((ap2+bp+c)×p+d−ax3)\quad = \mod((ap^2+bp+c)\times p +d-ax^3)
    • =mod  (mod  (ap2+bp+c)×p+d+m−mod  (ax3))\quad = \mod(\mod(ap^2+bp+c)\times p +d+m-\mod(ax^3))
    • =mod  (curr×p+d+m−mod  (ax3))\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);
    }
};