[ Rabin-Karp rolling hash ] Rabin-Karp 字串hash演算法

Michael O. Rabin和Richard M. Karp在1987年提出一個想法，即可以對模式串進行哈希運算並將其哈希值與文本中子串的哈希值進行比對。
設字串陣列為$S[n]$，字元編號為$0$到$n-1$
首先建立陣列$Hash[n+1]$，$Hash[i]$表示
$(S[0]*P^{i-1}+S[1]*P^{i-2}+...+S[i-1])\%PM,Hash[0]=0$,其中$P$跟$PM$是質數
假設要取編號$L$到編號$R$左閉右開區間的hash值，則其為$(Hash[R]-Hash[L]*P^{R-L})\%PM$
如果要用double hash則用不同質數計算兩種不同的hash值，用pair拼起來即可
以下提供模板:

	template <unsigned P, unsigned PM> class RollingHash {
	static vector<unsigned> Base;
	vector<unsigned> Hash;
	using LL = long long;
	public:
	RollingHash(const string &S) : Hash(S.size() + 1) {
	if (Base.empty())
	Base.resize(1, 1);
	for (size_t i = 1; i <= S.size(); ++i)
	Hash[i] = (LL(Hash[i - 1]) * P + S[i - 1]) % PM;
	while (Base.size() < Hash.size())
	Base.emplace_back((LL(Base.back()) * P) % PM);
	}
	size_t size() const { return Hash.size() - 1; }
	const vector<unsigned> &getHash() const { return Hash; }
	unsigned hash() const { return Hash.back(); }
	unsigned hash(unsigned L, unsigned R) const {
	return (Hash[R] + PM - (LL(Hash[L]) * Base[R - L]) % PM) % PM;
	}
	};
	template <unsigned P, unsigned PM> vector<unsigned> RollingHash<P, PM>::Base;

view raw rolling_hash.cpp hosted with ❤ by GitHub