字符串Hash 学习笔记
(Hash) 算法是一个好东西，在一些情况下可以取代一些比较难字符串算法，如(kmp)，(AC)自动机……
(Hash) 算法的精髓在于将较大的数转化为较小的数。
其实字母和符号的本质也是 (ACSII) 码，一个字符串的 (ACSII) 码输出来可以看做一个很大数。
然而这并没有什么用，因为这个数和字符串的本质还是相同的，根本无法让问题变得好处理，这时我们便想到了取模，因为取模有冲突，所以我们通过模较大的素数来减少冲突。
所以字符串 (Hash) 就是将字母或符号的 (ACSII) 码看做一个(n(n>字符集的数量))进制数下的数。
(base) 是进制数（(base>max(s[i]))），(s[i]) 是字符串，写过快读的同学肯定发现这东西和快读很像，是的快读就是将字符串转化为十进制数的过程。
再加上取模，很容易就可以求出一个字符串的 (Hash) 值，两个字符串的 (Hash) 值相同，在很大程度上我们就可以认为这两个字符串相同。
但是 (Hash) 能干的不止这些，利用一些数学知识，(Hash) 可以 (Theta(1)) 求出已经处理好的字符串的任意一段区间的 (Hash) 值。
其中 (base^{r-l+1}) 可以预处理，因为在模意义下 (Hash[r]) 可能小于 (Hash[l]) ，所以要加上 (MOD) ，再模 (MOD) 。
这样是怎样实现的呢？？
我们考虑怎样让十进制数下的 (12345) ，拿出 (34) ，比较容易的做法就是直接用 (1234\%100) ，但这样在模运算下是不可行的。
因为模运算可以转化为减运算，其实我们发现上面的运算可以转化为 (1234-12*10^2) 。这样的话在 (n) 进制和模运算下都适用，只不过需要处理一下像上面的问题就可以了。
上面说过 (Hash) 可能有冲突，在实现时往往适用双模 (Hash) 来实现，就是再加一个模数，做和上面一样的操作，只有两个 (Hash) 值都分别等于要判断的串的 (Hash) 值的时候才认为两个串相同。
每次拿出第一个串最后的长度为第二个串的字符串的 (Hash) 值判断是否和第二个串的 (Hash) 值相同，如果相同就跳回去。
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e6+100,MOD=1e9+7;
char s[N],a[N],ans[N];
ll Hash[N],p[N];
int base=233;
inline void pre()
{
int ls=strlen(s+1);
p[0]=1;
for (int i=1;i<=ls;i++)
p[i]=p[i-1]*base%MOD;
return ;
}
int main()
{
scanf("%s%s",s+1,a+1);
pre();
int ls=strlen(s+1),la=strlen(a+1);
ll will=0;
for (int i=1;i<=la;i++)
will=(will*base%MOD+a[i])%MOD;
int num=0;
for (int i=1;i<=ls;i++)
{
++num;
Hash[num]=(Hash[num-1]*base%MOD+s[i])%MOD;
ans[num]=s[i];
if (num>=la)
{
ll now=(Hash[num]-Hash[num-la]*p[la]%MOD+MOD)%MOD;
if (now==will)
num-=la;
}
}
for (int i=1;i<=num;i++)
printf("%c",ans[i]);
return 0;
}
(Hash) 也可以 (Theta(1)) 将两个字符串的 (Hash) 值拼接为一个。
其中 (pos) 是字符串在 ([l,r]) 的任意一个断点， (r-pos) 就是后面的那段字符串的长度。
怎样证明考虑上面的证明方式。