字符串哈希

字符串哈希的目的就是将字符串通过哈希函数映射到整数,然后进行其他操作。

一般来说我们使用进制哈希,给出一个固定进制 base,将一个串的每一个元素看做一位上的数字,然后这个串就可以看做一个 base 进制的数,这个数就是这个串的哈希值。通过对比每个串的的哈希值,即可判断两个串是否相同。

由于值域可能非常非常大,所以我们要在运算过程中对一个很大很大很大的质数取模才能避免碰撞。代码如下:

ull hash(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod;
    return ans;
}

KMP 算法

视频教程:https://www.bilibili.com/video/BV1Ys411d7yh

写得很好的一篇博客:https://blog.csdn.net/v_july_v/article/details/7041827

KMP 要实现的就是对于一个模式串 P,在给定字符串 S 中进行匹配。

考虑朴素的匹配方法:每次匹配失败都要把 S 的指针往回退重新匹配,复杂度在最坏的情况下可达 O(nm),在数据规模很大的时候会死掉。

所以 KMP 算法应运而生,KMP 可以 O(n+m) 求出模式串在主串中的匹配。为什么他能如此神奇,是因为指向 S 的指针不会往回退,利用神奇的 next 数组来进行模式串上的跳动。

  • 定义一个字符串 s 的 border 为其一个真子串 t,满足 t 既是 s 的前缀也是其后缀。

进行 KMP 算法时有一个很重要的数组 next,代表的就是 s[0~i-1] 的最大 border 的长度(即最大相等前后缀的长度),next 数组的初始化方式如下:

void get_next()
{
    int i=0,j;//定义两个指针
    next[0]=j=-1;
    while(i<lenp)
    {
        if(j==-1 || p[i]==p[j])//如果成功匹配或者实在没办法匹配了
            next[++i]=++j;
        else j=next[j];//往前跳 
    }
    return;
}

KMP 时如果匹配到某个位置发现失配了,那么 j 直接回退到 next[j] 就可以了,因为前后缀是已经匹配好了的。

void kmp()
{
    int i=0,j=0;
    while(i<lens)
    {
        if(j==-1 || s[i]==p[j])
            ++i,++j;
        else
            j=next[j];
        if(j==lenp)//说明匹配好了
            printf("%d\n",i-j+1),j=next[j];//打印结果并回退
    }
}
最后修改日期:2020年10月5日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。