S2 - 字符串哈希

c++11 string 通过进制角度得到字符串哈希值

class string_hash {
	string s;
	ullong ar[maxn + 1] {};
	ullong bin[maxn+1] {1ULL};
	const ullong base = 131ULL;
public:
	explicit string_hash(string &str):s(move(str)) {
		for (int i = 0; i < s.length(); i++) {
			ar[i + 1] = ar[i] * base + s[i];
			bin[i+1] = bin[i] * base;
		}
	}
	ullong hash(const int l, const int r) {
		return ar[r] - ar[l] * bin[r - l];
	}
};

Notes

base的经验取值为131、13331
类型使用unsigned long long, 对2^64取模，溢出即取模
l, r类似于begin(), end(), hash(l, r)返回子串[l, r)的哈希值

字符串哈希的运用

运用哈希方法解决字符串模式匹配问题

class strhash {
	ullong ar[maxn + 1] {};
	ullong bin[maxn + 1] {1ULL};
	const ullong base = 131ULL;
	const int len;
public:
	explicit strhash(string &tar): len(tar.length()) {
		for (int i = 0; i < len; i++) {
			ar[i + 1] = ar[i] * base + tar[i];
			bin[i + 1] = bin[i] * base;
		}
	}
	int solve(string &s) {
		ullong val = 0ULL;
		int cnt = 0;
		for (ullong i : s) (val *= base) += i;
		for (int l = 0, r = s.length(); r <= len; ++l, ++r)
			if (ar[r] - ar[l] * bin[s.length()] == val) ++cnt;
		return cnt;
	}
};

Notes

bin[0]必须初始化为1
对于题目的具体要求不同, 适当修改count_patterns函数即可
如果有必要, 哈希值相同的情况下应进一步判断是否真正相等