前言

hhh我讨厌hash！

码风不喜勿喷。

正文

哈希

题目传送门

哈希是一种将任意长度的数据通过哈希函数映射为固定长度的唯一值的技术，用于快速检索和数据完整性验证。总的来说就是通过一个固定的转换方式，将相同的串使其的哈希值一定相同，不同的串尽可能不同。当不同的串的哈希值相同时，这就发生了哈希冲突，我们需要避免冲突。

比如这道题，就是一个最基础的进制哈希。我们可以将字符串看成一个固定进制base进制的数，然后通过取模进行映射，最后按照题目要求进行操作。

Code：

#include<bits/stdc++.h>
#define int long long
#define B 233
#define mod 10000000007
using namespace std;
int n;
set<int> se;
string s; 
int hush(string x){
	int res=0;
	for(int i=0;i<x.size();i++)
	res=(res*B%mod+x[i])%mod;
	return res;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>s;
    	se.insert(hush(s));
	}
	cout<<se.size();
}

当然，如果想要更保险，比如这道题，我们就可以写两个像这样的哈希来避免冲突：

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define mod1 1000000007
#define mod2 1000000009
#define B1 233
#define B2 179
using namespace std;
int n,h1[N],f1[N],h2[N],f2[N];
string s;
int hash1(int l,int r){
    int x=(h1[r]-h1[l-1]*f1[r-l+1])%mod1;
    if(x<0)x+=mod1;
    return x;
}
int hash2(int l,int r){
    int x=(h2[r]-h2[l-1]*f2[r-l+1])%mod2;
    if(x<0)x+=mod2;
    return x;
}
signed main(){
    cin>>s;
    s='#'+s;
    f1[0]=f2[0]=1;
    for(int i=1;i<s.size();i++){
        h1[i]=(h1[i-1]*B1+s[i]-'a'+1)%mod1;
        f1[i]=f1[i-1]*B1%mod1;
        h2[i]=(h2[i-1]*B2+s[i]-'a'+1)%mod2;
        f2[i]=f2[i-1]*B2%mod2;
    }
    cin>>n;
    while(n--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(hash1(l1,r1)==hash1(l2,r2)&&hash2(l1,r1)==hash2(l2,r2))printf("Yes\n");
        else printf("No\n");
    }
}

字典树

题目传送门

先来一张图：

Trie 树，即字典树，是一种树形结构。典型应用是用于统计和排序大量的字符串前缀来减少查询时间，最大限度地减少无谓的字符串比较。

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

上图就是一个字典树。

知道原理后，我们就可以依照写出代码：

添加：

void insert(string x){
	int pos=0;
	for(int i=0;i<x.size();i++){
		if(a[pos][x[i]]==0)a[pos][x[i]]=++idx;
		pos=a[pos][x[i]];
		ans[pos]++;
	}
}

查询：

int query(string x){
	int pos=0;
	for(int i=0;i<x.size();i++){
		if(!a[pos][x[i]])return 0;
		pos=a[pos][x[i]];
	}
	return ans[pos];
}

反正字典树主要就是这两块，其他就比较好写了。（hhh总结一句就是以空间换时间。）

Manacher

题目传送门

先不看数据范围，我们可以得出这道题的最最最最暴力的代码：

for(int i=0;i<s.size();i++){
	for(int j=i;j<s.size();j++){
		bool flag=1;
		for(int k=i;k<=j;k++)
		if(s[i+j-k]!=s[k])flag=0;
		if(flag)ans=max(ans,j-i+1);
	}
}

发现这道题可以通过枚举中间点来分类长度是奇数还是偶数，然后通过while循环延展长度并取max，于是我们就可以得出这样的代码：

for(int i=0;i<s.size();i++){
	int d=0;
	while(i-d>=0&&i+d<s.size()&&s[i-d]==s[i+d]){
		ma=max(ma,d*2+1);
		d++;
	}
	int d=0;
	while(i-d>=0&&i+d+1<s.size()&&s[i-d]==s[i+d+1]){
		ma=max(ma,d*2+1);
		d++;
	}
}

（其实还可以在字符串的每个字符中间和字符串前后加上'#'，这样可以直讨论一种情况（ma/2），但是因为差不多所以就不写了。）

接下来我们要引出两个数组：maxr&mid！

maxr表示当前回文串能拓展到的最右边界，mid表示最右边界对应的中心点。

此外，我们还要用一个p数组来表示i的回文串。

接下来我们就要分情况了，首先是当i<=maxr，则p[i]=min(p[mid*2-i],maxr-i+1);当i>maxr时，p[i]=1。

接下来就要开始暴力扩展&更新mid和maxr了。具体就看代码吧！

#include<bits/stdc++.h>
#define N 22000005
using namespace std;
string s,s1;
int p[N],jmx;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>s1;
	s="#";
	for(int i=0;i<s1.size();i++)s.push_back(s1[i]),s.push_back('#');
	int maxr=0,mid=0;
	for(int i=0;i<s.size();i++){
		if(i<=maxr)p[i]=min(p[mid*2-i],maxr-i+1);
		else p[i]=1;
		while(i-p[i]>=0&&i+p[i]<s.size()&&s[i-p[i]]==s[i+p[i]])p[i]++;
		if(i+p[i]-1>maxr)maxr=i+p[i]-1,mid=i;
		jmx=max(jmx,p[i]*2-1);
	}
	cout<<jmx/2<<"\n";
}

KMP

题目传送门

首先只要学到这里的人应该都知道这道题的暴力代码，但是复杂度为O(n*m)，十分耗时。

可是慢在哪呢？

于是Knuth、Morris和Pratt提出来：慢在让i调回去！

知道了后可是怎么优化呢？

于是Knuth、Morris和Pratt提出来：我们可以使i不动，让j动！

所以，KMP算法核心是：通过调整 j，使得在 i 不变的前提下，i 和 j 依旧满足定义。

于是他们就创造了个next数组，定义是当第i位可以匹配，第i+1位无法继续匹配时，在j继续符合定义，即s1(i−j+1,i)与s2(1,j)完全相等的情况下，能调整到的最大的j。

算法流程如下：

  • 如果当前字符相等且j不为0，说明可以继续匹配，更改j和nxt[i]。
  • 如果不相等且j不为0，则一直往前跳知道可以为止，并更改j和nxt[i]
  • 如果j为0，只更改nxt[i]。

时间复杂度O(n+m)。

#include<bits/stdc++.h>
using namespace std;
int nxt[10000005];
string s1,s2;
int main(){
    cin>>s1>>s2;
    int n1=s1.size(),n2=s2.size();
    s1='#'+s1;
    s2='#'+s2;
    int j=0;
    for(int i=2;i<=n2;i++){
        while(j&&s2[i]!=s2[j+1])j=nxt[j];
        if(s2[i]==s2[j+1])j++;
        nxt[i]=j;
    }
    j=0;
    for(int i=1;i<=n1;i++){
        while(j&&s1[i]!=s2[j+1])j=nxt[j];
        if(s1[i]==s2[j+1])j++;
        if(j==n2){
            cout<<i-j+1<<"\n";
            j=nxt[j];
        }
    }
    for(int i=1;i<=n2;i++)cout<<nxt[i]<<" ";
}

练习题

P4421 [COCI 2017/2018 #1] Lozinke

题目传送门

题意

给出n个字符串，问有多少组字符串使得一个字符串为另一个字符串的子串。

思路

一眼哈希。。。直接看成27进制用哈希处理（最好使用双哈希，本文使用单哈希），把每个串扔进map，然后直接暴力枚举每个大串的子串是否是其他的大串就好了啊hhh。

代码
#include<bits/stdc++.h>
#define int long long
#define B 27 
using namespace std;
map<int,int> mp,vis;
int n,h[20005][15],ans;
string s[20005];
int gethash(int i,int l,int r){return (h[i][r]-h[i][l-1]*pow(B,r-l+1));}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		s[i]="#"+s[i];
		int len=s[i].size()-1;
		for(int j=1;j<=len;j++)
		h[i][j]=(h[i][j-1]*B+s[i][j]-'a'+1);
		mp[h[i][len]]++;
	}
	for(int i=1;i<=n;i++){
		int len=s[i].size()-1;
		mp[h[i][len]]--;
		vis.clear();
		for(int p=1;p<=len;p++)
		for(int q=p;q<=len;q++){
			int hash=gethash(i,p,q);
			if(!vis[hash]&&mp[hash]>0){
				ans+=mp[hash];
				vis[hash]=1;
			}
		}
		mp[h[i][len]]++;
	}
	cout<<ans<<"\n";
}

P7469 [NOI Online 2021 提高组] 积木小赛

题目传送门

题意

给定两个字符串，求问在第一个字符串取子序列，第二个字符串取子串，并使相等的不相同方案数。（两个方案相同，当且仅当这两个字符串大小相同且每一个位置上的字母都对应相同。）

思路

至少子串比子序列限制大，于是我们可以暴力枚举子串，并求出对应哈希值，最后再排序去重取最后数量即可。

代码
#include<bits/stdc++.h>
#define mod1 1000000007
#define mod2 1000000009
#define B1 233
#define B2 179
#define int long long
#define N 5005
using namespace std;
int n,tot;
pair<int,int> h[N*N];
string a,b;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>a>>b;
    a='#'+a;
    b='#'+b;
    for(int i=1;i<=n;i++){
        int has1=0,has2=0,k=1;
        for(int j=i;j<=n;j++){
            while(k<=n&&a[k]!=b[j])k++;
            if(k>n)break;
            k++;
            has1=(has1*B1+b[j]-'a'+1)%mod1;
            has2=(has2*B2+b[j]-'a'+1)%mod2;
            h[++tot]=make_pair(has1,has2);
        }
    }
    sort(h+1,h+1+tot);
    cout<<unique(h+1,h+tot+1)-h-1;
}

P10469 后缀数组

题目传送门

题意

给定一个长度为 n 字符串 S，下标从 0 至 n−1。将 S 的所有后缀（即截取 i∼n−1 这段子串）按字典序排序后，假设排名为 i 的后缀是从 j 这个位置截取到 n−1 的，则数组 sa[i]​=j，求出 sa 数组。还有一个 Height 数组，Height[i]​ 的值为：排名为 i 的后缀与排名为 i−1 的后缀的最长公共前缀长度。Height[1]​=0。

思路

求取sa数组，容易想到排序。但是如果正常排序会超时，于是我们可以使用哈希+二分把单次询问优化到O（log n）。如果前 x 个字符串可以匹配，则前 y(y<x) 个字符串也可以匹配；如果前 x 个字符串不可以匹配，则前 y(y>x) 个字符串也不可以匹配。所以这里的优化是正确的。

既然求出sa数组了，那height也很好求了。

代码
#include<bits/stdc++.h>
#define int long long
#define N 300005
#define m1 1000000007
#define m2 1000000009
#define b1 233
#define b2 179
using namespace std;
int n,sa[N],h1[N],h2[N],f1[N],f2[N];
string s;
int gethash1(int l,int r){
	int x=(h1[r]-h1[l-1]*f1[r-l+1])%m1;
	if(x<0)x+=m1;
	return x;
} 
int gethash2(int l,int r){
	int x=(h2[r]-h2[l-1]*f2[r-l+1])%m2;
	if(x<0)x+=m2;
	return x;
} 
int get(int x,int y){
	int l=1,r=min(n-x+1,n-y+1)+1;
	while(l<r){
		int mid=(l+r)/2;
		if(gethash1(x,x+mid-1)!=gethash1(y,y+mid-1)||gethash2(x,x+mid-1)!=gethash2(y,y+mid-1))r=mid;
		else l=mid+1;
	}
	return l;
}
bool cmp(int x,int y){int p=get(x,y);return s[x+p-1]<s[y+p-1];}
signed main(){
	cin>>s;
	n=s.size();
	s='#'+s;
	f1[0]=f2[0]=1;
	for(int i=1;i<=n;i++){
		h1[i]=(h1[i-1]*b1+s[i]-'a'+1)%m1;
		f1[i]=f1[i-1]*b1%m1;
		h2[i]=(h2[i-1]*b2+s[i]-'a'+1)%m2;
		f2[i]=f2[i-1]*b2%m2;
		sa[i]=i;
	}
	sort(sa+1,sa+1+n,cmp);
	for(int i=1;i<=n;i++)cout<<sa[i]-1<<' ';
	cout<<"\n";
	for(int i=1;i<=n;i++)cout<<get(sa[i],sa[i-1])-1<<' ';
	cout<<"\n";
}

P9606 [CERC2019] ABB

题目传送门

题意

给定一个字符串，问至少要在字符串末加多少个字符，使原串变成回文串。

思路

其实很简单，我们先正着和反着做一遍哈希，然后枚举回文中心就好了。

当然，这道题还可以使用KMP算法（最长后缀为next[n]）和manacher算法（字符串倒序后，i从0开始时f(i)=i+1 是目前最长回文是后缀的的充要条件），可以自己思考。

代码

此处为哈希代码。

#include<bits/stdc++.h>
#define int long long
#define mod1 1000000007
#define mod2 1000000009
#define B1 233
#define B2 179
#define N 400005
using namespace std;
int n;
string s;
int h1[N],h2[N],dh1[N],dh2[N],f1[N],f2[N];
int hash1(int l,int r){
    int x=(h1[r]-h1[l-1]*f1[r-l+1])%mod1;
    if(x<0)x+=mod1;
    return x;
}
int hash2(int l,int r){
    int x=(h2[r]-h2[l-1]*f2[r-l+1])%mod2;
    if(x<0)x+=mod2;
    return x;
}
int dhash1(int l,int r){
    int x=(dh1[l]-dh1[r+1]*f1[r-l+1])%mod1;
    if(x<0)x+=mod1;
    return x;
}
int dhash2(int l,int r){
    int x=(dh2[l]-dh2[r+1]*f2[r-l+1])%mod2;
    if(x<0)x+=mod2;
    return x;
}
bool check(int l1,int r1,int l2,int r2){
    return dhash1(l1,r1)==hash1(l2,r2)&&dhash2(l1,r1)==hash2(l2,r2);
}
signed main(){
    cin>>n>>s;
    n=s.size();
    s='#'+s;
    f1[0]=f2[0]=1;
    for(int i=1;i<=n;i++){
        h1[i]=(h1[i-1]*B1+s[i]-'a'+1)%mod1;
        h2[i]=(h2[i-1]*B2+s[i]-'a'+1)%mod2;
        f1[i]=f1[i-1]*B1%mod1;
        f2[i]=f2[i-1]*B2%mod2;
    }
    for(int i=n;i>=1;i--){
        dh1[i]=(dh1[i+1]*B1+s[i]-'a'+1)%mod1;
        dh2[i]=(dh2[i+1]*B2+s[i]-'a'+1)%mod2;
    }
    for(int i=n/2+1;i<=n;i++){
        int tmp=n-i+1;
        if(i-tmp>0&&check(i-tmp,i-1,i,n)){
            cout<<i-tmp-1<<"\n";
            break;
        }
        if(i-tmp+1>0&&check(i-tmp+1,i,i,n)){
            cout<<i-tmp<<"\n";
            break;
        }
    }
}

P4391 [BalticOI 2009] Radio Transmission 无线传输

题目传送门

题意

给定长度为 L 的字符串 s1​，你需要找到一个尽量短的 s1​ 前缀 s2​，使得 s1​ 是 s2​s2​…s2​ 的子串。

思路

这道题哈希解法其实很简单，枚举子串长度，用哈希判断是否相等即可。

可是这道题其实还能用KMP做hhh。

设最短的长度为x，那么前x个next数组的值为0，next[x+1]=1，next[x+2]=2,以此类推。因此，n-next[n]就是x的值。

代码

哈希：

for(int i=1;i<=n;i++){
    bool flag=1;
    for(int j=1;i*j<n;j++){
        int st=i*j+1,ed=min(n,i*j+i);
        if(hash1(1,ed-st+1)!=hash1(st,end)||hash2(1,ed-st+1)!=hash2(st,end)){
            flag=0;
            break;
        }
    }
    if(flag){
        cout<<i<<"\n";
        break;
    }
}

KMP：

#include<bits/stdc++.h>
using namespace std;
int nxt[1000005],n;
string s;
int main(){
    cin>>n>>s;s='#'+s;
    int j=0;
    for(int i=2;i<=n;i++){
        while(j&&s[i]!=s[j+1])j=nxt[j];
        if(s[i]==s[j+1])j++;
        nxt[i]=j;
    }
    cout<<n-nxt[n]<<"\n";
}

后记

历时2week完成，我讨厌哈希！

# 哈希算法 # 算法 # c++
Logo
EazyDevelop社区

一站式 AI 云服务平台

更多推荐

cover

Claude Code 辅助 RPA 脚本生成：零代码 RPA 进阶，突破规则自动化局限

avatar EazyDevelop社区
cover

零代码搭建+原生支付+MCP支持：这款开源项目，凭什么让企业级AI应用不再赔钱？

avatar EazyDevelop社区
cover

跨境电商运营有哪些关键环节？七大核心模块全拆解

avatar EazyDevelop社区