目录
虽然标题是 Hash ，但本篇文章不会仅仅注重于 Hash 算法。
要求读者的是掌握 Hash 的思想以及简单应用，同时牢固掌握字符串 Hash 。
同时本篇文章也简单讲述了离散化和Manacher（马拉车）算法。
请读者放心食用。
Hash 表又称散列表，是一种基于 链表+哈希函数 实现的算法，与离散化思想类似。
当我们要对若干复杂信息进行统计时，可以用 Hash 函数将其映射到一个简单的、容易维护的值域。
因为值域简单，所以容易发生冲突，所以要处理这种冲突情况。
这里仅介绍最常用的拉链法，有兴趣的同学可以自寻百度寻找其它方法。
最常用的方法就是链表存储，就是人们常说的拉链法或链地址法，下图就是简单的存储之后的样子。
本来没打算讲的，但是既然和 Hash 思想类似，就当做入门吧。
离散化其实就是缩小值域最直接的方法：排序后按编号赋值。（例如 1,30,69,51,5 变成 1,3,5,4,2）
一般离散化有三个步骤：
给一道例题好好体会：有一个序列a，每次操作给出（l,r），询问a中值在l和r之间的数的和。
代码见下：
int main() {
for (int i = 1; i <= n; ++i)
b[i] = a[i];
sort(b+1, b+n+1);
int m = unique(b+1, b+n+1) - (b+1);
for (int i = 1; i <= n; ++i) {
int v = a[i];
a[i] = lower_bound(b+1, b+m+1, v) - b;
c[a[i]] += v;
}
for (int i = 1; i <= m; ++i)
s[i] = s[i-1] + c[i];
while (q--) {
scanf("%d%d", &l, &r);
l = lower_bound(b+1, b+m+1, l) - b;
r = lower_bound(b+1, b+m+1, r) - b - 1;
printf("%d\n", s[r] - s[l-1]);
}
}个人认为这就是很基础的 Hash （如果这都理解不了就别学 Hash 了吧）
可以到百度去看看离散化，加深一下理解，对学习 Hash 有帮助。
Hash 的基本结构有两个：
当 Hash 函数设计的好的时候，所有元素几乎平均地位于每一个表头，即几乎不产生冲突。
此时查询的期望值是 \(O(1)\) 的。
在这里，普通 Hash 指的是整数类型的 Hash。 （后面会讲到运用广泛的字符串 Hash 算法）
最直接的思想是设计一个较大的质数 \(P\) ，令 \(Hash(x)=(x\) \(mod\) \(P)+1\) 。（加一是避免有 \(0\) 的产生）
此时所有数值都分布于 \(1\)~\(N\) 之中。
这种 Hash 思想简单，易于实现，这里不做过多的介绍。
简单例题，这里我们定义的 Hash 函数：\(H(a_1,a_2...a_n)=(\sum_{j=1}^{6} a(i,j)+\prod_{j=1}^{6} a(i,j) )mod\) \(P\)。
其中 P 是某个较大的质数，直接上代码吧。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 100010
#define MOD 99991
using namespace std;
int n,a[10],show[N][10],head[N],next[N],tot=0;
bool equal(int x){
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
bool flag=true;
for(int k=0;k<6;k++) if(a[(i+k)%6]!=show[x][(j+k)%6]) flag=false;
if(flag) return true;
flag=true;
for(int k=0;k<06;k++) if(a[(i+k)%6]!=show[x][(j-k+6)%6]) flag=false;
if(flag) return true;
}
}
return false;
}
int H(){
int sum=0;
long long mul=1;
for(int i=0;i<6;i++){
sum=(sum+a[i])%MOD;
mul=(mul*(long long)a[i])%MOD;
}
return (sum+mul)%MOD;
}
bool insert(){
int val=H();
for(int i=head[val];i;i=next[i]){
if(equal(i)) return true;
}
tot++;
for(int i=0;i<6;i++) show[tot][i]=a[i];
next[tot]=head[val];
head[val]=tot;
return false;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=0;j<6;j++) scanf("%d",&a[j]);
if(insert()){printf("Twin snowflakes found.\n");return 0;}
}
printf("No two snowflakes are alike.\n");
return 0;
}下面介绍的是一种可以把任意长度（最好不要太长，一般 \(<=1e6\)）的字符串转变成一个非负整数。
特点：碰撞概率几乎为0。（因此不需要链表结构防止冲突）
一般有以下步骤预处理字符串 Hash:
通常我们取 \(P=131/P=13331\) ，此时冲突的概率极低。（一般不会构造数据去卡你，因为很难构造）
通常我们取 \(M=2^{64}\) ，即 \(unsigned\) \(long\) \(long\) 的最大值，所以使用该类型存储 \(Hash(A)\) 。
如果 \(Hash(A)>2^{64}\) 会自动溢出，正好符合取余运算，同时避免了低效的 % 运算。
有以下两种运算：
举个栗子：\(S="abc",c="d",T="xyz"\) ，则：
根据以上两种操作可知，\(O(N)\) 的预处理前缀 Hash 值后，即可 \(O(1)\) 地判断两个字符串是否相同。
前缀和不会我也没办法，自行百度吧
字符串 Hash 模板题，初学者必做。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define N 1000010
using namespace std;
char s[N];
int m;
unsigned long long f[N],p[N];
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
scanf("%d",&m);
p[0]=1;
for(int i=1;i<=n;i++){
f[i]=f[i-1]*131+(s[i]-'a'+1);
p[i]=p[i-1]*131;
}
for(int i=1;i<=m;i++){
int l1,r1,l2,r2;
scanf("%d %d %d %d",&l1,&r1,&l2,&r2);
if(f[r1]-f[l1-1]*p[r1-l1+1]==f[r2]-f[l2-1]*p[r2-l2+1]) printf("Yes\n");
else printf("No\n");
}
return 0;
}这里仅仅讲述 Hash 思想，因为有算法复杂度更优的 \(Manacher\) 算法。
思想就是枚举每个回文子串的中心位置 \(i=1\)~\(N\) ，分情况讨论奇数和偶数长度，
接着二分答案枚举字符串长度，利用字符串 Hash 判断两个字符串是否相同。（需要一个前缀数组和一个后缀数组）
不断刷新 \(ans=min(ans,len)\) ，复杂度 \(O(n\) \(log\) \(n)\) 。
下一段我们将讨论优秀的 \(Manachar\) 算法，可以 \(O(n)\) 解决最长回文子串的问题。
思路是先处理 \(SA[]\) 数组，初始化为 \(SA[i]=i\) 接着以字典序排序。（方法见下）
假设已经排好序了，我们就来求两个字符串的最长公共前缀，同样可以二分答案地去找。
发现可以将其写作函数，返回值为最长公共前缀的长度，那么 \(SA[]\) 数组排序时只需要 return(s[a+len]<s[b+len])
其中 \(a,b\) 为 \(cmp\) 函数的两个参数，\(len\) 是其最长公共前缀的长度，至此本问题得到完美解决。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 300010
using namespace std;
int sa[N],height[N],n;
unsigned long long p[N],H[N];
char s[N];
unsigned long long find(int a,int b){
return (H[b]-H[a-1]*p[b-a+1]);
}
int len(int a,int b){
if(s[a]!=s[b]) return 0;
int l=0,r=n-1-max(a,b);
while(l<r){
int mid=(l+r+1)>>1;
if(find(a,a+mid)==find(b,b+mid) && a+mid<n && b+mid<n)
l=mid;
else r=mid-1;
}
return l+1;
}
bool cmp(int a,int b){
int l=len(a,b);
return s[a+l]<s[b+l];
}
int main(){
scanf("%s",s);
n=strlen(s);
p[0]=1;
H[0]=s[0]-'a'+1;
for(int i=1;i<n;i++){
sa[i]=i;
p[i]=p[i-1]*131;
H[i]=H[i-1]*131+(s[i]-'a'+1);
}
sort(sa,sa+n,cmp);
for(int i=0;i<n;i++) printf("%d ",sa[i]);
printf("\n0 ");
for(int i=1;i<n;i++) printf("%d ",len(sa[i],sa[i-1]));
return 0;
}给定一个字符串，求出其最长回文子串。例如：
以上问题的传统思路大概是，遍历每一个字符，以该字符为中心向两边查找。其时间复杂度为 ，效率很差。
1975 年，一个叫 Manacher 的人发明了一个算法，\(Manacher\) 算法（中文名：马拉车算法）。
下面来看看马拉车算法是如何工作的。
由于回文分为偶回文（比如 bccb）和奇回文（比如 bcacb），而在处理奇偶问题上会比较繁琐，所以这里我们使用一个技巧，具体做法是：在字符串首尾，及各字符间各插入一个字符（前提这个字符未出现在串里）。
举个例子：s="abbahopxpo"，转换为s_new="$#a#b#b#a#h#o#p#x#p#o#"。（这里的字符 $ 只是为了防止越界，下面代码会有说明）
如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#p#o#，长度都转换成了奇数。
定义一个辅助数组int p[]，其中p[i]表示以 i 为中心的最长回文的半径，例如：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s_new[i] | $ | # | a | # | b | # | b | # | a | # | h | # | o | # | p | # | x | # | p | # |
| p[i] | 1 | 2 | 1 | 2 | 5 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 4 | 1 | 2 | 1 |
经事后提醒发现表格缺少了7以后的部分，并且目前没有好的解决办法，可以自行点击原文链接查看，不过应该不影响阅读
可以看出，p[i] - 1正好是原字符串中最长回文串的长度。
接下来的重点就是求解 p 数组，如下图：
设置两个变量，mx 和 id 。mx 代表以 id 为中心的最长回文的右边界，也就是mx = id + p[id]。
假设我们现在求p[i]，也就是以 i 为中心的最长回文半径，如果i < mx，如上图，那么：
if (i < mx)
p[i] = min(p[2 * id - i], mx - i);2 * id - i为 i 关于 id 的对称点，即上图的 j 点，而p[j]表示以 j 为中心的最长回文半径，因此我们可以利用p[j]来加快查找。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char s[1000];
char s_new[2000];
int p[2000];
int Init()
{
int len = strlen(s);
s_new[0] = '$';
s_new[1] = '#';
int j = 2;
for (int i = 0; i < len; i++)
{
s_new[j++] = s[i];
s_new[j++] = '#';
}
s_new[j] = '\0'; // 别忘了哦
return j; // 返回 s_new 的长度
}
int Manacher()
{
int len = Init(); // 取得新字符串长度并完成向 s_new 的转换
int max_len = -1; // 最长回文长度
int id;
int mx = 0;
for (int i = 1; i < len; i++)
{
if (i < mx)
p[i] = min(p[2 * id - i], mx - i); // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
else
p[i] = 1;
while (s_new[i - p[i]] == s_new[i + p[i]]) // 不需边界判断，因为左有'$',右有'\0'
p[i]++;
// 我们每走一步 i，都要和 mx 比较，我们希望 mx 尽可能的远，这样才能更有机会执行 if (i < mx)这句代码，从而提高效率
if (mx < i + p[i])
{
id = i;
mx = i + p[i];
}
max_len = max(max_len, p[i] - 1);
}
return max_len;
}
int main()
{
while (printf("请输入字符串：\n"))
{
scanf("%s", s);
printf("最长回文长度为 %d\n\n", Manacher());
}
return 0;
}文章开头已经提及，Manacher 算法为线性算法，即使最差情况下其时间复杂度亦为\(O(n)\) 。
在进行证明之前，我们还需要更加深入地理解上述算法过程。
根据回文的性质，p[i]的值基于以下三种情况得出：
（1）：j 的回文串有一部分在 id 的之外，如下图：
假设右侧新增的紫色部分是p[i]可以增加的部分，那么根据回文的性质，a 等于 d ，也就是说 id 的回文不仅仅是黑线，而是黑线+两条紫线，矛盾，所以假设不成立，故p[i] = mx - i，不可以再增加一分。
（2）：j 回文串全部在 id 的内部，如下图：
根据代码，此时p[i] = p[j]，那么p[i]还可以更大么？答案亦是不可能！见下图：
假设右侧新增的红色部分是p[i]可以增加的部分，那么根据回文的性质，a 等于 b ，也就是说 j 的回文应该再加上 a 和 b ，矛盾，所以假设不成立，故p[i] = p[j]，也不可以再增加一分。
（3）：j 回文串左端正好与 id 的回文串左端重合，见下图：
根据代码，此时p[i] = p[j]或p[i] = mx - i，并且p[i]还可以继续增加，所以需要
while (s_new[i - p[i]] == s_new[i + p[i]])
p[i]++;根据（1）（2）（3），很容易推出 Manacher 算法的最坏情况，即为字符串内全是相同字符的时候。在这里我们重点研究 Manacher() 中的 for 语句，推算发现 for 语句内平均访问每个字符 5 次，即时间复杂度为：\(T_{worst}(n)=O(n)\)。
同理，我们也很容易知道最佳情况下的时间复杂度，即字符串内字符各不相同的时候。推算得平均访问每个字符 4 次，即时间复杂度为：\(T_{best}(n)=O(n)\)。
综上，Manacher 算法的时间复杂度为 \(O(n)\)。
以上内容全部转载自原文链接，确实写的很好。
感谢 LZshuing 给了我灵感，以及让我入门 Hash。
感谢 \(Manacher\) 部分作者的优秀文章，再上原文链接。
感谢您的观看，同时这篇文章希望对您有帮助。
原文：https://www.cnblogs.com/lpf-666/p/12445980.html