今天我们来谈谈字符串哈希在NOIP等算法竞赛方面的应用。
先来看一道例题 luogu3370，可以说是很水了。
我用了两种做法AC了它。
首先两种做法都用到了一个操作，就是用一个整数来表示一个字符串。这个操作很简单，设一个指数，如我设了131，那么我们就把字符串当成一个131进制数，然后换算成十进制的数，就是它哈希时候的代表值。
然后我们发现代表值不能太大，所以我们要取膜域。我们为了避免冲突，通常还会用乘法哈希，就是把这个值乘上一个大质数，然后取膜，然后还要判断冲突，如果当前位置已有冲突，就取下一个位置。但实际上字符串哈希出现冲突的概率是很小的，除非出题人刻意出了鬼畜的数据来卡字符串哈希，否则基本不会出事。比如例题我就没有处理冲突直接ac了。
取膜域有两种做法：
第一种是在竞赛中较为常用的溢出型hash，利用unsigned long long 自然溢出实现取膜。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; unsigned long long base=131; int N,arr[10005]; char st[1600]; int hash(char ch[]) { unsigned long long ans=0; int len=strlen(ch); for(int i=0;i<len;i++) ans=ans*base+ch[i]; return ans; } int main() { int ans=0; scanf("%d",&N); for(int i=1;i<=N;i++) { scanf("%s",st); arr[i]=hash(st); } sort(arr+1,arr+1+N); for(int i=2;i<=N;i++) if(arr[i]!=arr[i-1]) ans++; cout<<ans+1; }
第二种是自己找一个大质数，然后直接取膜
我的大质数可以让程序-1s哦~
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define modl 19260817*19890604-19491001 using namespace std; long long base=131; int N,arr[10005]; char st[1600]; int hash(char ch[]) { long long ans=0; int len=strlen(ch); for(int i=0;i<len;i++) ans=ans*base+ch[i],ans%=modl; return ans; } int main() { int ans=0; scanf("%d",&N); for(int i=1;i<=N;i++) { scanf("%s",st); arr[i]=hash(st); } sort(arr+1,arr+1+N); for(int i=2;i<=N;i++) if(arr[i]!=arr[i-1]) ans++; cout<<ans+1; }