字符串哈希

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 679 字

多项式哈希映射大数，前缀哈希取子串

字符串
字符串哈希

前置内容

正文

// 字符串哈希：映射成大数
// 多项式哈希：逐位加权
// 双哈希降低冲突概率
// 例：比较两子串是否相同
#include <cstdio>
#include <cstring>
typedef unsigned long long ull;
char s[100005];
ull h[100005], p[100005];
int n, base = 131;
// 预处理前缀哈希与幂
void build() {
    p[0] = 1;
    // 递推：h[i]=h[i-1]*base+s[i]
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * base
            + (s[i] - 'a' + 1);
        p[i] = p[i - 1] * base;
    }
}
// 取子串 [l,r] 的哈希值
ull get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    build();
    // 比较 1..3 与 4..6 是否同
    if (get(1, 3) == get(4, 6))
        printf("YES");
    else printf("NO");
    return 0;
}

字符串哈希

前置内容

正文

CSP-J · 编程模板的其它内容