题意

使用指定的hash函数，返回给定字符串s第一个长度为k的hash值 = 给定hashVal的子串的下标。

方法

hashNew=val(s[first])+power∗(hashNow−val(s[last])∗power^(k−1)

代码

class Solution {
public:
    int indexChar(char s)
    {
        return (int)(s - 'a') + 1;
    }

    int fastPow(int a, int b, int mod)
    {
        long long pow_res = 1;
        long long aa = a;
        while (b) {
            if (b & 1) pow_res *= aa;
            aa *= aa;
            aa %= mod;
            b >>= 1;
        }
        return pow_res;
    }

    string subStrHash(string s, int power, int modulo, int k, int hashValue) {
        int N = s.size();
        int index_pos = 0, index_ans = 0;
        vector<long long> pow_vec;
        string test_str(s, N-k, k);
        long long test_res = 0;
        for (int i = 0; i < k; i++) {
            test_res += (fastPow(power, i, modulo) * indexChar(test_str[i])) % modulo;
        }
        test_res %= modulo;
        int p = fastPow(power, k-1, modulo);
        for (int i = N-1; i > k-1; i--) {
            if (test_res == hashValue) index_ans = i;
            cout << test_res << endl;
            test_res -= (p * indexChar(s[i]));
            test_res += modulo;
            test_res *= power;
            test_res %= modulo;
            test_res += indexChar(s[i-k]);
            test_res %= modulo;
        }
        if (test_res == hashValue) index_ans = k-1;
        return s.substr(index_ans-k, k);
        // return s.substr(0, k);
    }
};