本文涉及知识点

滚动哈希
C++算法：滑动窗口及双指针总结

LeetCode2156. 查找给定哈希值的子串

给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：
hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + … + val(s[k-1]) * p^k-1) mod m.
其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val(‘a’) = 1 到 val(‘z’) = 26 。
给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。请你返回 s 中 第一个 长度为 k 的 子串 sub ，满足 hash(sub, power, modulo) == hashValue 。
测试数据保证一定 存在 至少一个这样的子串。
子串 定义为一个字符串中连续非空字符组成的序列。

示例 1：
输入：s = “leetcode”, power = 7, modulo = 20, k = 2, hashValue = 0
输出：“ee”
解释：“ee” 的哈希值为 hash(“ee”, 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0 。
“ee” 是长度为 2 的第一个哈希值为 0 的子串，所以我们返回 “ee” 。
示例 2：

输入：s = “fbxzaad”, power = 31, modulo = 100, k = 3, hashValue = 32
输出：“fbx”
解释：“fbx” 的哈希值为 hash(“fbx”, 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32 。
“bxz” 的哈希值为 hash(“bxz”, 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32 。
“fbx” 是长度为 3 的第一个哈希值为 32 的子串，所以我们返回 “fbx” 。
注意，“bxz” 的哈希值也为 32 ，但是它在字符串中比 “fbx” 更晚出现。
提示：
1 <= k <= s.length <= 2 * 10⁴
1 <= power, modulo <= 10⁹
0 <= hashValue < modulo
s 只包含小写英文字母。
测试数据保证一定 存在 满足条件的子串。

滚动哈希

vP[i] = powerⁱ
vHash[i] = s[0]*vP[i-1] + s[1]*vP[i-2] $\cdots$ s[i-1]*vP[0] 即s[0…i-1]逆序的hash。
即 ∑ j : 0 i − 1 ( s [ j ] × v P [ i − 1 − j ] ) \sum_{j:0}^{i-1}(s[j]\times vP[i-1-j]) ∑j:0i−1​(s[j]×vP[i−1−j])
vHash[i]*vP[len] = ∑ j : 0 i − 1 ( s [ j ] ∗ v P [ i − 1 + l e n − j ] ) \sum_{j:0}^{i-1}(s[j]*vP[i-1+len-j]) ∑j:0i−1​(s[j]∗vP[i−1+len−j]) 式子一
vHash[i+len-1] = ∑ j : 0 i + l e n − 1 ( s [ j ] × v P [ i + l e n − 1 − j ] ) \sum_{j:0}^{i+len-1}(s[j]\times vP[i+len-1-j]) ∑j:0i+len−1​(s[j]×vP[i+len−1−j]) 式子二
式子二减去式子一
∑ j : i i + l e n − 1 ( s [ j ] × v P [ i + l e n − 1 − j ] ) \sum_{j:i}^{i+len-1}(s[j]\times vP[i+len-1-j]) ∑j:ii+len−1​(s[j]×vP[i+len−1−j])
令k = j - i
∑ k : 0 l e n − 1 ( s [ k + i ] × v P [ l e n − k − 1 ] ) \sum_{k:0}^{len-1}(s[k+i] \times vP[len-k-1]) ∑k:0len−1​(s[k+i]×vP[len−k−1])
令i1 = len-1
删除s的前i个字符：
即： ∑ j : 0 i 1 ( s [ k ] × v P [ i 1 − j ] ) \sum_{j:0}^{i1}(s[k]\times vP[i1-j]) ∑j:0i1​(s[k]×vP[i1−j]) 即删除前i+1字符后vHash[len-1]
即hash(s.substr(i,len), p, m) 即s[i…i+len-1]的逆序的哈希。
令s的逆序为s1，则s[l…i+len-1]在s1对应的下标为[n -1- (i+len-1),n-1-i] 换算成左闭右开就是：[n -1- (i+len-1),n-1-i+1)

代码

核心代码

namespace TMP {
	
	class CHashStr {
	public:
		CHashStr(int mod,string s, int iCodeNum, int iCodeBegin = 1, char chBegin = 'a'):MOD(mod){
			m_c = s.length();
			m_vP.resize(m_c + 1);
			m_vP[0] = 1;
			m_vHash.resize(m_c + 1);
			const int P = iCodeBegin + iCodeNum;
			for (int i = 0; i < m_c; i++)
			{				
				m_vHash[i + 1] =  ( ((long long)m_vHash[i] * P)%MOD + s[i] - chBegin + iCodeBegin)% MOD;
				m_vP[i + 1] =((long long) m_vP[i] * P) % MOD;
			}
		}
		int GetHashExincludeRight(int left, int right)
		{			
			const auto i1 = ((long long)m_vHash[left] * m_vP[right - left]) % MOD;
			const int i2 = (m_vHash[right] - i1 + MOD) % MOD;
			return i2;
		}
		int m_c;
		vector<int> m_vP;
		vector<int> m_vHash;
		const int MOD;
	};
}

class Solution {
public:
	string subStrHash(string s, int power,const int modulo, int k, int hashValue) {
		const int N = s.length();
		TMP::CHashStr has(modulo,string(s.rbegin(),s.rend()),power-1);
		for (int i = 0; i + k <= N; i++) {
			const auto cur = has.GetHashExincludeRight(N-1-(i+k-1),N-1-i+1);
			if (cur == hashValue) {
				return s.substr(i, k);
			}
		}
		return "";
	}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}



namespace UnitTest
{
	string s;
	int power,  modulo,  k,  hashValue;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod01)
		{
			s = "eet", power = 7, modulo = 20, k = 2, hashValue = 0;
			auto res = Solution().subStrHash(s, power, modulo, k, hashValue);
			AssertEx(string("ee"), res);
		}
	
		TEST_METHOD(TestMethod00)
		{
			s = "lee", power = 7, modulo = 20, k = 2, hashValue = 0;
			auto res = Solution().subStrHash(s, power, modulo, k, hashValue);
			AssertEx(string("ee"), res);
		}
		TEST_METHOD(TestMethod0)
		{
			s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0;
			auto res = Solution().subStrHash(s, power, modulo, k, hashValue);
			AssertEx(string("ee"), res);
		}
		TEST_METHOD(TestMethod1)
		{
			s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32;
			auto res = Solution().subStrHash(s, power, modulo, k, hashValue);
			AssertEx(string("fbx"), res);
		}
	};
}