$$Hash$$
【引言】：
由于(yjk)写了(Hash)博客，我才想起来我还有个(Hash)没写完，真是太尴尬了。
【(about)】：
也就是我们什么时候会用到(Hash) ， 和用(Hash)的重大好处 ， 及其缺点
对于哈希来说。当我们遇到字符串匹配的类型（当然，(KMP)大法更好）和其他有关于字符串之间比较的问题这类的问题， 我们往往用哈希解决
哈希可以在大约在线性的复杂度内可以找到答案， 也是比较方便的， 挺快的对吧。
问题也随之而来， 我们无法保证哈希的正确性是百分之百， 一定会有一定的错误概率， 后文将予以说明
【工作原理】：
哈希是怎么运行的呢？ 其实也是很简单。
我们可以看一下下面这一个图，
我们首先可以有这么一个思路， 也就是我们这个字符串转化成数字，然后把他看成一个 (p)进制位数 ， 我们在这里假设母串中(A ,B ,C , D ,……Z) 我们认为他们对应着(1 , 2 , 3,4…… 26) ,对应多少都一样， 这里是为了简洁， 我们认为他是(p)进制数 ， 那么(ABC)也就是 ，$ p ^ 3 imes 1 + p ^2 imes 2 + p ^ 1 imes 3$ ， 那么在这时候我们去匹配的时候 ， 发现很神奇的事情， 那就是，只要这个P是个质数才能满足我们所说的正确性， 如果(p)不是质数，那么他一定可以被(a)整除， 那么 (p^1 就是 a^k)次方， 或者是(p ^1 = a imes k) ,这样的话， 不是(p)进制数， 同样的， 不同字符串出现相同的概率就会增加
为什么会出现相同的哈希值（我们把这个东西称为hash值）呢？ ，很简单 ，$5 ^ 1 imes 4 = 20 = 5^0 imes 20 $ ,我们这东西是不进位的， 所以会出现相同的数字 。 其正确性不保证，但是我们可以用两个模数来进行比较，那么这样的概率就会大大增加， 其中不必对其去模 ，(2^{64}) 让其自然溢出 ， 就相当于去模了。那么自然，敢在(Codeforces)写自然溢出的都是猛士 ，
为了避免其错误出现的概率 ， 我们采用双(hash) ,也就是设(sum_1 , sum_2) ,然后挨着比较即可，倒也没什么难得，但是不要以为这样就万事无忧了，认为是无错，你只要写(hash)，就有错的可能性。只不过是大点还是小点的问题罢了。
【题目】：
【描述】：给定一个字符串(A)和一个字符串(B),求(B)在(A)中的出现次数。(A)和(B)中的字符均为英语大写字母或小写字母。
我们就可以将其转化成哈希值，比较一下 ，就好了。
【code】:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define int unsigned long long
using namespace std ;
const int maxn = 1e6 + 10;
const int mod = 10007 ;
const int p = 133 ;
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
char a[maxn] , b[maxn] ;
int sum[maxn] ;
int s ;
int power[maxn] ;
int ans ;
int n , m ;
void init() //处理子串和母串
{
//题目给定均为大写或者小写， 故不必进行大小写转化
n = strlen(a + 1) ;
m = strlen(b + 1) ;
power[0] = 1 ;
for(int i = 1 ; i < 1000000 ; i ++)
{
power[i] = power[i - 1] * p ;//处理 p的n的次方
//cout<<power[i] <<endl ;
}
sum[0] = 0 ;
for(int i = 1 ; i <= n ; i++) //处理处母串
{
sum[i] = sum[i - 1] * p + (unsigned)(a[i] - 'A' + 1) ;
}
for(int i = 1 ; i <= m ; i++)
{
s = s * p + (unsigned)(b[i] - 'A' + 1 ) ;
}
}
signed main()
{
cin >> a+1 >>b+1 ;
init() ; //预处理
for(int i = 0 ; i <= n - m ; i ++)
{
//sum中记录的是前缀，我们需要乘以一个 p的m次方
//让他们对齐，手模一下更好理解
if(s == sum[i + m ] - sum[i] * power[m])
{
ans ++ ;
}
}
cout<<ans<<endl ;
return 0 ;
}
【哈希表】：
有关(Hash)表，类比一下存图时的链式前向星存图，我们其实很容易的发现和链式前向星的存法有很大的相似性。
首先，说明一下 ， 只有用到能够支持插入字符串的时候，才用到(hash)表，其他情况下是用不到的。
当然，如果是支持插入字符串的时候，我们可以用自动机来完成这一道题。(hash)能够做的最大优势的一种题，就是，查找循环节。
【工作流程】 ：
这就看一下代码吧，能理解。我去搜搜，工作流程，写起来很麻烦。
(here).
这里我用的双hash,其(x,y)分别为两个(hash)函数产生的(hash)值
【Code】:
插入 ：
void insert(int x, int y)
{
nxt[++tot] = head[x] ;
head[x] = tot;
en[tot] = y ;
}
查询 ：
bool query(int x, int y)
{
for (int i = head[x] ; i ; i = nxt[i])
{
if (en[i] == y)
{
return true ;
}
}
return false ;
}
然后就行了，你就又行了。
【应用】 ：
查找循环节
【题意】 ：给定一个字符串，多次询问其某个子串的最短循环节。
可以发现对于字符串串 (s[l,r])，如果长度为 (x) 的前缀是 (s[l,r]) 的一个循环节，则必有 (len(s[l,r])|x) 且 (s[l,r-x]=s[l+x,r])
如果存在长度为 $y$ 的前缀是 $s$ 的循环节， $y$ 是 $x$ 的因数且 $x$ 是串长的因数（ $x|y, len(s)|x$），则长度为 $x$ 的前缀必然是 $s$ 的循环节（感性理解一下）。 考虑筛出每个数的最大质因数， $O(log n)$ 分解质因数，然后从大到小试除，看余下的长度是否是循环节，如果是则更新答案.
【Code】:
/*
by : Zmonarch
知识点 ： 哈希
思路 ： 1. 循环节的长度也必能被乘除
2. 显然，我们去其最小质因数分解更优，处理出质因数， 直接除枚举
3.删除一个循环节， 其中其他的字符， 再乘上p^len , 应该与
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#define int unsigned long long
using namespace std ;
const int kmaxn = 5e5 + 10 ;
const int kmaxm = 2e6 + 10 ;
const int p = 1e3 + 7 ;
const int mod = 13331 ;
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , ans , len ;
char s[kmaxn] ;
int power[kmaxn] , sum[kmaxn] , prime[kmaxn] , vis[kmaxn];
void prepare() //先处理出 p的n次方和哈希值
{
memset(vis , false , sizeof(vis)) ;
power[0] = 1 ;
for(int i = 1 ; i <= n ; i++)
{
power[i] = power[i - 1] * p ;
}
sum[0] = 0 ;
for(int i = 1 ; i <= n ; i++)
{
sum[i] = sum[i - 1] * p + ( s[i] -'A' + 1 ) ;
}
}
void prim() //利用线性筛，筛出最小质因数
{
for(int i = 2 ; i <= n ; i++)
{
if(vis[i]) continue ;
for(int j = 1 ; i * j <= n ; j++)
{
int t = i * j ;
if(vis[t]) continue ;
vis[t] = true ;
prime[t] = i ;
}
}
}
bool check(int l , int r , int k)
{
if(sum[r - k] - sum[l - 1] * power[r - k - l + 1] == sum[r] - sum[l + k - 1] * power[r - k - l + 1])
{
return true ;
}
else return false ;
}
signed main()
{
n = read() ;
cin >> s+1 ;
prepare() ;
prim() ;
int q = read() ;
for(int i = 1 ; i <= q ; i++)
{
int l = read() , r = read() ;
ans = len = r - l + 1 ;
while(len > 1) //不断进行循环，查找循环节
{
int k = ans / prime[len] ; //寻找循环节在什么地方
len /= prime[len] ;
if(check(l , r , k))
{
ans = k ;
}
}
printf("%d
" , ans) ;
}
return 0 ;
}
查找回文子串 ：
必然是不如(manacher)跑的快。
题目： 查找回文子串 ；
[]code]
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];//顺序Hash
return num2[r]-num2[l+1]*_base[l-r+1];//倒序Hash
}
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;//要求顺序Hash与倒序Hash匹配
else r=mid-1;
}
然后其他的忘了，想起来再补充。
【卡掉他】：
对于如何卡掉(hash),请看这篇博客
,我没有要当毒瘤的意愿，我选择不写。要是这篇博客说了，(hash)好，回头就卡你(hash),莫不是不太好。