c-Karp-Rabinrollinghash-skipandappendparts

Karp-Rabin滚动哈希算法将字符串视为一个数字。该算法可用于在字符串比较和搜索中快速查找匹配项。该算法包括跳过和附加部分，可以在不重复计算哈希值的情况下快速更新哈希值。

实现该算法的方法如下：

#define d 256 // 字符集大小

// 滚动哈希函数
int rolling_hash(char *pat, char *txt, int q) {
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0;  // 哈希值初始化为0
    int t = 0;  // 哈希值初始化为0
    int h = 1;

    // 找到 h 的值
    for (i = 0; i < M - 1; i++)
        h = (h * d) % q;

    // 计算模式串的哈希值 p 和文本串的初始化哈希值 t
    for (i = 0; i < M; i++) {
        p = (d * p + pat[i]) % q;
        t = (d * t + txt[i]) % q;
    }

    // 滚动哈希值
    for (i = 0; i <= N - M; i++) {
        // 如果哈希值匹配，检查模式串和文本串是否匹配
        if (p == t) {
            for (j = 0; j < M; j++) {
                if (txt[i+j] != pat[j])
                    break;
            }
            if (j == M)
                printf("Pattern found at index %d \n", i);
        }
        // 计算下一个哈希值
        if (i < N-M) {
            t = (d*(t - txt[i]*h) + txt[i+M])%q;
            if (t < 0)
                t = (t + q);
        }
    }
}

该算法具有O(N-M+1)的时间复杂度，并且可以在常数时间内操作。 它可以接受常数时间的变异，例如跳过和附加部分，以及开发Q-gram索引等其他数据结构。

以上就