2017-08-02

字符串哈希算法

文章目录

原文地址:https://ngunauj.github.io

前几天在做leetcode题目的时候，有个来是类似字符串匹配的题目，当时想到了kmp但是这么久没写kmp了已经不会求next数组了（唉～多半是我掌握的不好，所以才想不起来怎么写的）。还好我们有字符串哈希算法，处理字符串匹配的问题同样能达到O(n+m)的时间复杂度。

算法思想：假设原串a的长度n,要查找的串b的长度m,朴素的算法是遍历a的同时移动m个字符进行比较，总体的时间复杂度O（n*m）,但是当我们遍历S(取S中m个求哈希值)的同时可以用O(1)的得到T串的哈希值。时间复杂度就是O(n+m)。接下来就是如何进行哈希了。
选取两个合适的互素常数b和h(n<b<h),假设字符串$C=c_1c_2…c_m$,定义哈希函数：
$$H(C)=(c_1b^{m-1}+c_2b^{m-2}+c_3b^{m-3}+…c_mb^{0})mod\ {h}$$
其中b是基数，相当于把字符串看成b进制数。这样，字符串$S=s_1s_2…s_n$从位置k+1开始长度为m的字符串子串S[k+1,k+m]的哈希值，就可以利用从位置k开始的字符串子串S[k..k+m-1]的哈希值，直接进行如下计算。

$$H(S[k+1..k+m])=(H(S[k..k+m-1])×b-s_kb^m+s_{m+k})mod\ {h}$$
于是，只要不断这样计算开始位置右移一位后的字符串子串的哈细致，就可以在O(n)时间内得到所有位置对应的哈希值。在写代码时，可以用用64位无符号整数计算哈希值，通过自然溢出省去求模运算。$h=2^{64}$
这种利用滚动哈希的字符串匹配算法叫Rabin-Karp算法。不过，原来的Rabin-Karp算法在哈希值相等的时，还要用传统的字符串比较算法判断字符串是否相等。

typedef unsigned long long ull;
const ull B = 100000007;
//a是否在b中出现
bool contain(string a, string b) {
    int al = a.length(), bl = b.length();
    if (al > bl) return false;
    //计算B的al次方
    ull t = 1;
    for (int i = 0; i < al; ++i) t *= B;
    //计算a和b长度为al的前缀对应的哈希值 初始化
    for (int i = 0; i < al; ++i) ah = ah * B + a[i];
    for (int i = 0; i < al; ++i) bh = bh * B + b[i];
    //对b不断右移一位，更新哈希值并判断
    for (int i = 0; i + al <= bl; ++i) {
        if (ah == bh) return true;
        if (i + a < bl) bh = bh * B + b[i + al] - b[i]*t;
    }
    return false;
}

当然，不光右移一位，对于左移一位、左端或右端加长一位或是缩短一位的情况，也能进行类似的处理。例如，假设要求S的后缀和T的前缀相等的最大长度，也可以利用滚动哈希在O(m+n)的时间内高效求得。

typedef unsigned long long ull;
const ull B = 100000007;
//a的后缀和b的前缀相等的最大长度
int overlap(string a, string b) {
    int al = a.length(), bl = b.length();
    int ans = 0;
    ull ah = 0, bh = 0, t = 1;
    for (int i = 1; i <= min(al, bl); ++i) {
        ah = ah + a[al - i] * t;
        bh = bh * B + b[i - 1];
        if (ah == bh) ans = i;
        t *= B;
    }
    return ans;
}

kmp也可以完美的解决这个问题。回头看看kmp。

赏

纯属好玩