難度分: 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);
}
};