字符串Hash学习笔记

时间：2020-01-27 19:43:46 阅读：57 评论：0 收藏：0 [点我收藏+]

------------恢复内容开始------------
请勿将字符串Hash和哈希表搞混。虽然两者都是哈希算法，但实现原理和应用上有很大区别。

以下默认字符串下标从1开始，用\(s[l,r]\)表示字符串\(s\)的第\(l\)到第\(r\)个字符组成的子串。

概述

字符串Hash常用于各种字符串题目~~的部分分~~中。字符串Hash可以在\(O(1)\)时间内完成判断两个字符串的子串是否相同。通常可以用这个性质来优化暴力以达到骗分的目的。

一、什么字符串Hash

字符串Hash其实本质上是一个公式：
\[Hash(s)=(\sum_{i=1}^{len}{s[i]\cdot b^{len-i}})mod\ m\]
其中\(b,m\)是常量。

是不是感觉很像一个生成函数

那为什么要采用这样一个长得像生成函数的式子呢？

参照哈希表，我们知道如果两个字符串的Hash值相同，那么这两个串大概率是相同的。

但事实上我们常常需要截取一个字符串的子串。可以发现，对于\(s[l,r]\)这个子串的Hash值
\[Hash(s[l,r])=(\sum_{i=l}^{r}{s[i]\cdot b^{r-i}})\mod m\]
考虑原串\(s\)的前缀和
\[Hash(s[1,r])=(\sum_{i=1}^{r}{s[i]\cdot b^{r-i}})\mod m\]
\[Hash(s[1,l-1])=(\sum_{i=1}^{l-1}{s[i]\cdot b^{l-i-1}})\mod m\]
于是可以推出：\(Hash(s[l,r])=Hash(s[1,r])-Hash(s[1,l-1])\cdot b^{r-l+1}\)

当然这都是在模\(m\)意义下。

于是对于原串记录Hash前缀和，就可以\(O(1)\)截取子串Hash值

二、字符串Hash的用处

字符串Hash是一种十分暴力的算法。但由于它能\(O(1)\)判断字符串是否相同，所以可以骗取不少分甚至过掉一些字符串题。

接下来先介绍字符串Hash与其他字符串算法的对比。

1.字符串匹配(KMP)

这个不用说了，枚举起始点扫一遍\(O(n)\)解决，时间复杂度和KMP相同。

2.回文串

考虑以同一个字符为中心的回文串的子串一定是回文串，所以满足可二分性。

将字符串正着和倒着Hash一遍，如果一个串正着和倒着的Hash值相等则这个串是回文串。枚举每个节点为回文中心，二分即可。

时间复杂度相比较manacher较劣，为\(O(n\log n)\)。~~发现过不了模板题。~~

关键代码

ull num[22000000],num2[22000010];
ull find_hash(int l,int r)
{
    if(l<=r)
    return num[r]-num[l-1]*_base[r-l+1];
    return num2[r]-num2[l+1]*_base[l-r+1];
}


int l=0,r=min(i-1,len-i);
int len=0;
while(l<=r)
{
    int mid=(l+r)>>1;
    if(find_hash(i,i+mid)==find_hash(i,i-mid)) l=mid+1,len=mid;
    else r=mid-1;
}

3.LCP(最长公共前缀)

LCP也具有可二分性。对于\(s_1,s_2\)，和两个前缀长度\(j,i\)，\(j<i\)，其中\(i\)是\(s1,s2\)的前缀，则\(j\)也是\(s1,s2\)的前缀。

所以可以在\(O(\log n)\)时间求出两个串的前缀。

例：后缀排序

仿照上述求lcp的方式，因为决定两个字符串的大小的是他们lcp的后一个字符，所以用快排加二分求lcp即可做到\(O(n\log^2n)\)的时间复杂度。比SA多了一个\(\log\)。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#define base 233
#define ull unsigned long long
using namespace std;
ull bases[1000010],hashs[1000010];
char str[1000010];
int n;
inline ull get(int l,int r){return hashs[r]-hashs[l-1]*bases[r-l+1];}
bool cmp(int l1,int l2)
{
    int l=-1,r=min(n-l1,n-l2);
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(get(l1,l1+mid)==get(l2,l2+mid)) l=mid;
        else r=mid-1;
    }
    if(l>min(n-l1,n-l2)) return l1>l2;
    else return str[l1+l+1]<str[l2+l+1];
}
int a[1000010];
int main()
{
    scanf("%s",str+1);
    n=strlen(str+1);
    bases[0]=1;
    for(int i=1;i<=n;i++)
    {
        bases[i]=bases[i-1]*base;
        hashs[i]=hashs[i-1]*base+str[i];
        a[i]=i;
    }
    stable_sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}

难道字符串Hash只能去水其他算法的题吗？不！暴力有时不只是骗分的！

1.求字符串的循环节

例：OKR-A Horrible Poem

题意：求一个字符串的子串的最短循环节。

可以发现对于串\(s[l,r]\)，如果\(x\)是子串的一个循环节，必有\((r-l+1)\mod x=0\) 且 \(s[l,r-x]=s[l+x,r]\)

如果存在长度\(y\)是\(s\)的循环节（\(y\)是\(x\)的因数）且\(x\)是串长的约数，则\(x\)必然是\(s\)的循环节。

考虑筛出每个数的最大质因数，然后\(O(\log n)\)分解质因数，然后从大到小试除，看余下的长度是否是循环节，如果是则更新答案。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define N 500010
#define base 233
#define ull unsigned long long
using namespace std;
char str[N];
int len;
ull hashs[N],bases[N];
void make_hash(void)
{
    bases[0]=1;
    for(int i=1;i<=len;i++)
    {
        hashs[i]=hashs[i-1]*base+str[i]-'a'+1;
        bases[i]=bases[i-1]*base;
    }
}
ull get_hash(int l,int r){return hashs[r]-hashs[l-1]*bases[r-l+1];}
int prime[N],nxt[N],cnt;
int num[N],tot;
int main()
{
    scanf("%d",&len);
    scanf("%s",str+1);
    make_hash();
    for(int i=2;i<=len;i++)
    {
        if(!nxt[i]) nxt[i]=prime[++cnt]=i;
        for(int j=1;j<=cnt && i*prime[j]<=len;j++)
        {
            nxt[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int lens=r-l+1;
        int ans=0;
        tot=0;
        while(lens>1)
        {
            num[++tot]=nxt[lens];
            lens/=nxt[lens];
        }
        lens=r-l+1;
        for(int j=1;j<=tot;j++)
        {
            int len1=lens/num[j];
            if(get_hash(l,r-len1)==get_hash(l+len1,r)) lens=len1;
        }
        printf("%d\n",lens);
    }
    return 0;
}

2.动态字符串查询

现在的大多数字符串算法（比如KMP,AC自动机,SAM,SA,PAM）大多都是静态的查询或者只允许在最后插入。但如果要求在字符串中间插入或修改，这些算法就无能为力了。

而字符串Hash的式子其实是可以合并的，只要知道左区间的Hash值，右区间的Hash值，和右区间的大小，就可以知道总区间的Hash值。这就使得字符串Hash可以套上很多数据结构来维护。

例1：火星人

题意：求两个后缀的lcp，动态插入字符和改字符。

用平衡树维护区间的Hash值，仿照上述求lcp的方法，时间复杂度\(O(n\log^2n)\)。

由于长度过长，只放主程序和关键代码。

inline void update(int u)
{
    siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;
    sum[u]=sum[ch[u][0]]*bases[siz[ch[u][1]]+1]+val[u]*bases[siz[ch[u][1]]]+sum[ch[u][1]];
}
int main()
{
    srand(19260817);
    scanf("%s",str+1);
    int m;
    scanf("%d",&m);
    n=strlen(str+1);
    bases[0]=1;
    for(int i=1;i<=100000;i++) bases[i]=bases[i-1]*base;
    for(int i=1;i<=n;i++) root=t.merge(root,t.new_node(str[i]-'a'+1));
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%s%d",opt,&x);
        if(opt[0]=='Q')
        {
            scanf("%d",&y);
            printf("%d\n",lcp(x,y));
        }
        else if(opt[0]=='R')
        {
            scanf("%s",opt);
            t.erase(root,x);
            t.insert(root,x-1,opt[0]-'a'+1);
        }
        else if(opt[0]=='I')
        {
            scanf("%s",opt);
            t.insert(root,x,opt[0]-'a'+1);
            n++;
        }
    }
    return 0;
}

例2：一道口胡的题

题意：维护一个字符串的子串的集合，一开始字符串和集合均为空。

要求完成：在集合中插入一个子串，在字符串末尾加一个字符，求集合中与当前询问的子串lcp最大值。

比如字符串为\(abbabba\)

集合中的子串为\(s[1,4],s[3,6],s[5,7]\)。

此时查询与子串\(s[2,5]\)，答案为2（\(s[2,5]\)和\(s[5,7]\)的lcp为2）。

\(m\leq 10^5\),强制在线（为了防止SA过而特意加的）。

（假如存在SAM的做法可以在下方评论）

首先，考虑一些暴力的做法：

暴力将一个子串和集合中的串用上述方法求lcp，时间复杂度\(O(m^2\log m)\)
暴力建trie，将子串挂到trie上，时间复杂度\(O(m^2)\)，空间\(O(m^2)\)

~~显然上述的方法都不可行。~~

考虑使用SA的想法，与一个串lcp最大的串一定是字典序最靠近它的串，也就是比它字典序大中最小的，和比它小中最大的。

仿照这个思路，使用上述比较两个串字典序大小的方法，考虑使用平衡树来维护子串集合中字典序的顺序，查询时只需查询前驱后继中的lcp最大值即可。

时间复杂度\(O(m\log^2m)\)

三、字符串Hash的缺点

虽然字符串Hash在暴力方面有极大的优势，但从它的名字中也可以看出它存在的缺点：Hash冲突。

Hash Killer II

题意大概就是卡单Hash的代码，且\(mod=10^9+7\)。

根据生日悖论，对于\(n\)个不同的字符串，假如你的\(mod\)很小（比如\(10^9+7\)），极有可能把其中两个判成相同。对于\(mod=N\)时错误的概率\(P\)，有技术分享图片（详见百度百科）

可以发现这个概率远大于\(n/N\)。

所以假如用自然溢出可能会被卡的情况下，建议写双Hash。但是需要注意一点，双Hash的常数十分之大。
------------恢复内容结束------------
请勿将字符串Hash和哈希表搞混。虽然两者都是哈希算法，但实现原理和应用上有很大区别。