Karp-rabin算法

#include<iostream> #include<string> using namespace std; string a; int al; string b; int bl; long long d = 1073741824; long long calcuStr(string tmp) { long long rst = 0; for (int i = 0; i < tmp.length(); i++) { rst += tmp[i] - 95 + i;//将字符串转为对应的数字，再加上他的位数，能有效减少散列冲突 } return rst % d;//（书上写的是将字符串转换为27进制，这样得到的数过大，不方便运算） } long long upDate(long long rst, char a, char b) { return rst - a + b;//更新a字符串匹配的那一段的hash值 } bool match() { int hashA = calcuStr(a.substr(0, bl)); int hashB = calcuStr(b); for (int i = 1; i < al - bl + 1; i++) { if (hashA == hashB) {//如果二者哈希值相等，再比较一下是不是真的匹配了 bool isEqual = true; for (int j = 0; j < bl; j++) { if (a[j + i - 1] != b[j]) { isEqual = false; break; } } if (isEqual) return true; } else { hashA = upDate(hashA, a[i - 1], a[i + bl - 1]);//未匹配，则后移 } } return false; } int main() { while (cin >> a >> b) { al = a.length(); bl = b.length(); cout << match() << endl; } }

关于哈希值更新算法的解释