经过K8的提醒我成功意识到我不应该学流因为我是菜狗

好像也是，我普及组OJ的状压，KMP，AC自动机都没打，单调队列优化DP最多勉强打几下的废物为啥学网络流去了

所以去打字符串Hash了

看看能不能打懂吧

坚持每天推歌直到不知道推啥为止

字符串Hash

诶我好像学过，哦我学的是KMP不是字符串哈希

定义一个把字符串映射到整数的函数 \(f\) ，称为Hash函数。

函数 \(f\) 可以帮我们判断两个字符串是否相等

思想

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。

然后字符串Hash也是如此

字符串Hash中，值域需要小到能够快速比较，因为存在哈希冲突，值域不能太小

性质

具体来说，哈希函数最重要的性质可以概括为下面两条：

• 在 Hash 函数值不一样的时候，两个字符串一定不一样；

• 在 Hash 函数值一样的时候，两个字符串不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。

哈希冲突： Hash 值一样但字符串不一样的现象

实现

对于一个长度为 \(l\) 的字符串 \(s\) 来说，我们可以这样定义 Hash 函数：
\(f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M\) 。例如，对于字符串 \(xyz\) ，其哈希函数值为 \(x\times b^2+y\times b+z\) 。

如何选择\(M\)和\(b\) \(?\)

\(M\)至少要比字符串中最大的字符要大，\(b\)可以随便选

//低效率版本
#define int long long
const int M=1e9+7;
const int B=13331;
inline int hash(const std::string&s){
    int res=0;
    for(int i=0;i<s.size();++i)
        res=(res*B+s[i])%M;
    return res;
}
bool cmp(const std::string&s,const std::string&t) {
    return hash(s)==hash(t);
}

优化

• 哈希冲突

  为了减少被毒瘤出题人卡的情况我们可以选择多\(\bmod\)几个大质数

  比如\(1e9+7\),\(1e9+9\),\(998244353\)

  不怕死的可以ull自然溢出但是我不敢

• 多次询问子串哈希

  先预处理出每个前缀的哈希值，将哈希值看成一个 \(b\) 进制的数对 \(M\) 取模的结果，每次就能快速求出子串的Hash值

  用 \(f_i(s)\) 表示 \(f(s[1..i])\) ，即原串长度为 \(i\) 的前缀的哈希值，那么有 \(f_i(s)=s[1]\cdot b^{i-1}+s[2]\cdot b^{i-2}+\dots+s[i-1]\cdot b+s[i]\)

  用类似前缀和的方式快速求出 \(f(s[l..r])\) ，有字符串 \(s[l..r]\) 的Hash值为 \(f(s[l..r])=s[l]\cdot b^{r-l}+s[l+1]\cdot b^{r-l-1}+\dots+s[r-1]\cdot b+s[r]\)

  \(f(s[l..r])=f_r(s)-f_{l-1}(s) \times b^{r-l+1}\)，因此可以快速得到子串的哈希值。其中 \(b^{r-l+1}\) 可以 \(O(n)\) 的预处理然后 \(O(1)\) 回答每次询问

好困啊接下来的后面再写