# 2156. Find Substring With Given Hash Value
###### tags: `Leetcode` `Medium` `Rolling Hash` `Sliding Window`
Link: https://leetcode.com/problems/find-substring-with-given-hash-value/description/
## 思路
fixed length sliding window
从后往前遍历 因为这样每次往前移一个单位 我们只要减去```最右边的数字*power^(k-1)``` 再整体乘上```power``` 再加上最左边的数字即可
## Code

class Solution {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int n = s.length();
        long curr = 0;
        int ans = -1;
        long highestPower = 1;
        for(int i=0; i<k-1; i++) highestPower = highestPower*power%modulo;
        for(int i=0; i<k; i++){
            curr = (curr*power%modulo+s.charAt(n-1-i)-'a'+1)%modulo;
        }
        if(curr==hashValue) ans = n-k;
        for(int i=n-k-1; i>=0; i--){
            curr = curr - (s.charAt(i+k)-'a'+1)*highestPower%modulo;
            curr = (curr+modulo)%modulo;
            curr = curr*power%modulo;
            curr = (curr+s.charAt(i)-'a'+1)%modulo;
            if(curr==hashValue) ans = i;
        }
        return s.substring(ans, ans+k);
    }
}