526互联

hash判断回文串

发布时间 2023-09-09 20:50:41作者: -37-

hash的计算方法参考《字符串哈希》

建立正反两向的字符串哈希数组

for (int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * P;
    h[i] = h[i - 1] * P + str[i]; // 
}
for (int i = n; i >= 1; i--) {
    L[i] = L[i + 1] * P + str[i]; // 
}

如果某一段字符串正向的hash值和反向的hash值相同，则这一段字符串是回文串

ULL checkH(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

ULL checkL(int l, int r) {
    return L[l] - L[r + 1] * p[r - l + 1];
}

if (checkH(l, r) == checkL(l, r)) {
	true;
} else {
	false;
}