字符串哈希
观看讲解视频：董晓算法 做的笔记
理论部分
字符串哈希 是把不同的字符串映射成不同的整数。
-
对于一个长度为 \(n\) 的字符串 \(s\)，我们定义它的 Hash 函数为：
\(h(s) = \Sigma ^n_{i=1}\) \(s[i] \times p^{n-i}\) \((mod\) \(m)\)
例如：字符串 \(abc\)，他的 hash 函数值为 \(ap^2+bp^1+cp^0\)
即 \(97\times131^2+98\times131^1+99\) -
如果两个字符串不一样，Hash 值却一样，这样的现象称为 哈希碰撞
-
解决哈希碰撞的方法：
保证 \(p\)、\(m\) 互质，\(p\) 通常取质数 \(131\) 或 \(13331\)；\(m\) 通常取大整数 \(2^64\)，哈希函数要定义为 ULL（unsigned long long），超过则自动溢出，等价于取模。
关于 unsigned long long：无符号，取值范围在 \(0 \sim 2^{64}\)
代码实现：
- 求一个字符串的哈希值：前缀和，
前缀和：\(h[i] = h[i-1] \times p + s[i]\)，\(h[0] = 0\) (\(h[i]\) 表示前 \(i\) 项的 hash 值)
时间复杂度：\(O(n)\) - 他的子串的哈希值就是区间和
区间和：\(h[l,r] = h[r] - h[l] \times p^{r-l+1}\)
时间复杂度：\(O(1)\)
例题：
P3370 【模板】字符串哈希
模板题，直接上代码。
#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
const int maxn=100010;
const int p=131;
int n;
int lens;
char s[maxn];
ULL ans[maxn],h[maxn];
int cnt=0;
ULL calc(char s[],int n)
{
h[0]=0;
for(int i=1;i<=lens;i++)
{
h[i]=h[i-1]*p+s[i]; //求 hash 值，前缀和，便于求区间 hash 值（虽然这题不需要 QWQ ）
}
return h[lens];
}
//计算哈希值
int main(){
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
lens=strlen(s+1);
ans[i]=calc(s,lens);//计算哈希值
}
sort(ans+1,ans+1+n);
for(int i=1;i<=n;i++)
{
if(ans[i]!=ans[i-1])cnt++;
}
cout<<cnt<<endl;
return 0;
}
魔族密码
题目意思：
求最长词链。（其实就是关于字符串的最长上升子序列了）
输入保证了字符串按字典序排列且没有重复的（太良心了）
词链：多个词组成的表中，前一个单词是后一个单词的前缀。
思路：
不是吧？？我这个蒟蒻都想起来了两种方法。。（虽然只会实现一种）
- 一看前缀，就是字典树
让节点的 cnt 值表示有多少个 s 在这里结尾
每次插入一个字符串，查找这个字符串经过节点的 cnt 值之和
跟原答案求一个 max 值
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;
int cnt=1;
struct node{
int son[65];
int cnt;
}z[3000100];
int getnumber(char ch)
{
return ch-'a'+1;
}
void insert(string s)
{
int now=1;
int cnt_s=1;
for(int i=0;i<s.length();i++)
{
int num=getnumber(s[i]);
if(!z[now].son[num])
cnt++,z[now].son[num]=cnt;
cnt_s+=z[now].cnt;
now=z[now].son[num];
}
z[now].cnt++;
ans=max(ans,cnt_s);
return;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
insert(s);
}
cout<<ans<<endl;
return 0;
}
- 但是
标签里有 哈希
考虑哈希做法，此处参考 https://www.luogu.com.cn/article/bu7eorhv
因为输入保证按照字典序排列，因此如果 \(s_j\) 是 \(s_i\) 的前缀，则必然会有 \(j < i\)。
这样在计算 \(h(s_i)\) 的值的时候，计算每个前缀和的时候，查找一下前面是否有这一个值就行了。
我们可以推出状态转移方程：\(dp_i = max\) \(\{{dp_i},{dp_j+ 1}\}\)
代码：我说没有行吗。。。（逃
其实是我不会