字符串Hash 学习笔记

╰半夏微凉° 2023-06-01 15:54 22阅读 0赞

#  #

字符串 \\(Hash\\)

\\(Hash\\) 算法是一个好东西，在一些情况下可以取代一些比较难字符串算法，如\\(kmp\\)，\\(AC\\)自动机……

\\(Hash\\) 算法的精髓在于将较大的数转化为较小的数。

其实字母和符号的本质也是 \\(ACSII\\) 码，一个字符串的 \\(ACSII\\) 码输出来可以看做一个很大数。

但是这并没有什么用，因为这个数和字符串的本质还是相同的根本无法  
让问题变得好处理，这时我们便想到了取模，因为取模有冲突，所以我们通过模较大的素数来减少冲突。

所以字符串 \\(Hash\\) 就是将字母或符号的 \\(ACSII\\) 码看做一个\\(n(n>字符集的数量)\\)进制数下的数。

\\\[Hash\[i\]=Hash\[i-1\]\*base+s\[i\]\\\]

\\(base\\) 是进制数（\\(base>\\max(s\[i\])\\)），\\(s\[i\]\\) 是字符串，写过快读的同学肯定发现这东西和快读很像，是的快读就是将字符串转化为十进制数的过程。

再加上取模，很容易就可以求出一个字符串的 \\(Hash\\) 值，两个字符串的 \\(Hash\\) 值相同，在很大程度上我们就可以认为这两个字符串相同。

[\\(Hash\\)的模板题][Hash]

但是 \\(Hash\\) 能干的不止这些，利用一些数学知识，\\(Hash\\) 可以 \\(\\Theta(1)\\) 求出已经处理好的字符串的任意一段区间的 \\(Hash\\) 值。

\\\[Hash\[l,r\]=(Hash\[r\]-Hash\[l-1\]\*base^\{r-l+1\}\\%MOD+MOD)\\%MOD\\\]

其中 \\(base^\{r-l+1\}\\) 可以预处理，因为在模意义下 \\(Hash\[r\]\\) 可能小于 \\(Hash\[l\]\\) ，所以要加上 \\(MOD\\) ，再模 \\(MOD\\) 。

这样是怎样实现的呢？？

我们考虑怎样让十进制数下的 \\(12345\\) ，拿出 \\(34\\) ，比较容易的做法就是直接用 \\(1234\\%100\\) ，但这样在模运算下是不可行的。

因为模运算可以转化为减运算，其实我们发现上面的运算可以转化为 \\(1234-12\*10^2\\) 。这样的话在 \\(n\\) 进制和模运算下都适用，只不过需要处理一下像上面的问题就可以了。

上面说过 \\(Hash\\) 可能有冲突，在实现时往往适用双模 \\(Hash\\) 来实现，就是再加一个模数，做和上面一样的操作，只有两个 \\(Hash\\) 值都分别等于要判断的串的 \\(Hash\\) 值的时候才认为两个串相同。

[一道比较简单的题目][Link 1]

每次拿出第一个串最后的长度为第二个串的字符串的 \\(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\\) 值拼接为一个。

\\\[Hash\[l,r\]=(Hash\[l,pos\]\*base^\{r-pos\}\\%MOD+Hash\[pos+1,r\])\\%MOD\\\]

其中 \\(pos\\) 是字符串在 \\(\[l,r\]\\) 的任意一个断点， \\(r-pos\\) 就是后面的那段字符串的长度。

怎样证明考虑上面的证明方式。

[「BalticOI 2014 Day 1」三个朋友][BalticOI 2014 Day 1]

转载于:https://www.cnblogs.com/last-diary/p/11437921.html

[Hash]: https://www.luogu.org/problem/P3370
[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=3942
[BalticOI 2014 Day 1]: https://loj.ac/problem/2823