字符串处理基本算法----字符串哈希

字符串匹配算法之字符串hash

我们平时在计数还有排序等基本操作中就经常会用到hash的思想，其本质就是将数值与需要操作的数据进行一一对应且不出现重复（重复这个算法就没意义了嘛）
既然一般的数字我们可以进行Hash，那么字符是否可以Hash呢？答案当然是肯定的！

为了更好地理解Hash，先给大家举个栗子，对与任意一个数字，我们将他转化为二进制之后可以表示成这样：
2(len[i]−1)∗num[i]+2(len[i−1]−1)∗num[i−1]...+20∗1∗num[0]=number $2^{(len[i]-1)}\ast num[i]+2^{(len[i-1]-1)}\ast num[i-1]...+2^0\ast 1\ast num[0]=number$

—-> 101010=25∗1+24∗0+23∗1+22∗0+21∗1+20∗0 $101010=2^5\ast 1+2^4\ast 0+2^3\ast 1+2^2\ast 0+2^1\ast 1+2^0\ast 0$

那么对于字符串我们一样可以进行相同的转化！

我们可以将 Hash[len] $Hash[len]$记为长度为 Len $Len$的前缀的 hash $hash$值

那么对于字符串 s $s$的某一段前缀，我们可以将他转化为如下形式

Hash[i]=s[1]∗xi+s[2]∗x(i−1)+...+s[i]∗x0 $Hash[i]=s[1]\ast x^i+s[2]\ast x^{(i-1)}+...+s[i]\ast x^0$

联系二进制数值的转化，我们发现我们需要一个底数以避免不同字符串有相同的 hash $hash$值，我们可以叫他 base $base$,

base $base$在这里我们一般取个131就够了，所以我要取个233（我就是要皮一下）

base $base$也不能随意取，一般我们取的是一个质数尽可能的减少 hash $hash$值相等的意外。

综上所述，对于 L $L$~ R $R$区间的字符串，他们的 hash $hash$值便为
Hash[R]−Hash[L]∗base(R−L+1) $Hash[R]-Hash[L]\ast bas{e}^{(R-L+1)}$

至此，字符串 hash $hash$的所有内容便讲完啦，是不是很简单！

下面是核心代码

ll base=233;

string s;

ll Hash[100005];
ll Base[100005];

void init()
{
    Base[0]=1;
    Hash[0]=0;
    for(int i=1;i<=100004;i++)
        Base[i]=Base[i-1]*base;
    for(int i=1;i<=s.size();i++)
        Hash[i]=Hash[i-1]*base+s[i]-' ';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
}