字符串Hash 学习笔记

字符串\(Hash\)

\(Hash\)算法是一个好东西，在一些情况下可以取代一些比较难字符串算法，如\(kmp\)，\(AC\)自动机……

\(Hash\)算法的精髓在于将较大的数转化为较小的数。

其实字母和符号的本质也是\(ACSII\)码，一个字符串的\(ACSII\)码输出来可以看做一个很大数。

但是这并没有什么用，因为这个数和字符串的本质还是相同的根本无法
让问题变得好处理，这时我们便想到了取模，因为取模有冲突，所以我们通过模较大的素数来减少冲突。

所以字符串\(Hash\)就是将字母或符号的\(ACSII\)码看做一个\(n(n>字符集的数量)\)进制数下的数。

\[Hash[i]=Hash[i-1]*base+s[i]\]

\(base\)是进制数（\(base>\max(s[i])\)），\(s[i]\)是字符串，写过快读的同学肯定发现这东西和快读很像，是的快读就是将字符串转化为十进制数的过程。

再加上取模，很容易就可以求出一个字符串的\(Hash\)值，两个字符串的\(Hash\)值相同，在很大程度上我们就可以认为这两个字符串相同。

\(Hash\)的模板题

但是\(Hash\)能干的不止这些，利用一些数学知识，\(Hash\)可以\(O(1)\)求出已经处理好的字符串的任意一段区间的\(Hash\)值。

\[Hash[l,r]=(Hash[r]-Hash[l-1]*base^{r-l+1}\%MOD+MOD)\%MOD\]

其中\(base^{r-l+1}\)可以预处理，因为在模意义下\(Hash[r]\)可能小于\(Hash[l]\)，所以要加上\(MOD\)，再模\(MOD\)。

这样是怎样实现的呢？？

我们考虑怎样让十进制数下的\(12345\)，拿出\(34\)，比较容易的做法就是直接用\(1234\%100\)，但这样在模运算下是不可行的。

因为模运算可以转化为减运算，其实我们发现上面的运算可以转化为\(1234-12*10^2\)。这样的话在\(n\)进制和模运算下都适用，只不过需要处理一下像上面的问题就可以了。

上面说过\(Hash\)可能有冲突，在实现时往往适用双模\(Hash\)来实现，就是再加一个模数，做和上面一样的操作，只有两个\(Hash\)值都分别等于要判断的串的\(Hash\)值的时候才认为两个串相同。

一道比较简单的题目

每次拿出第一个串最后的长度为第二个串的字符串的\(Hash\)值判断是否和第二个串的\(Hash\)值相同，如果相同就跳回去。

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e6+100,MOD=1e9+7;
char s[N],a[N],ans[N];
ll Hash[N],p[N];
int base=233;
inline void pre()
{
    int ls=strlen(s+1);
    p[0]=1;
    for (int i=1;i<=ls;i++)
    p[i]=p[i-1]*base%MOD;
    return ;
}
int main()
{
    scanf("%s%s",s+1,a+1);
    pre();
    int ls=strlen(s+1),la=strlen(a+1);
    ll will=0;
    for (int i=1;i<=la;i++)
    will=(will*base%MOD+a[i])%MOD;
    int num=0;
    for (int i=1;i<=ls;i++)
    {
        ++num;
        Hash[num]=(Hash[num-1]*base%MOD+s[i])%MOD;
        ans[num]=s[i];
        if (num>=la)
        {
            ll now=(Hash[num]-Hash[num-la]*p[la]%MOD+MOD)%MOD;
            if (now==will)
            num-=la;
        }
    }
    for (int i=1;i<=num;i++)
    printf("%c",ans[i]);
    return 0;
}

字符串Hash 学习笔记

原文：https://www.cnblogs.com/last-diary/p/11437921.html