在数学一本通上看过这两人名字，现在又出现了...
-
思想：
用一个整数表示一个字符串
(w_{str})=((a_0) (p^{n-1})+(a_1) (p^{n-2})+...+(a_{n-1}) (p^0)) ((MOD) (q))
-
注意：
字符转换成(a_n)时最好不要转为0，例如遇到"a","aa","aaa"的情况
-
优越之处：
我们可以在O(1)内取出任意子串的Hash值
怎么实现？
- 记录下所有前缀的Hash值
我们知道
(w_{pre_{i-1}}) (=() (a_0) (p^{i-1})+(a_1) (p^{i-2})+...+(a_{i-1}) (p^0)) ((MOD) (q))
(w_{pre_{j}}) (=() (a_0) (p^{j})+(a_1) (p^{j-1})+...+(a_{j}) (p^0)) ((MOD) (q))
所以
- (w_{str_{i,j}})
(=() (a_i) (p^{j-i})+(a_{i+1}) (p^{j-i-1})+...+(a_{j}) (p^0))
(=) (w_{pre_{j}}) (-) (w_{pre_{i-1}}) (p^{j-i+1}) ((MOD) (q))
然而....
在做TJOI2017 DNA时我发现取模太慢了,不如用unsigned long long自然溢出，这样一下就快了很多。
同时还有一个优化技巧,预处理出p值的幂,这样也能快不少。
-
应用：
-
字符串匹配
-
思路：
和KMP一样是(O(N+M))的时间复杂度，只需要遍历文本串比较哈希值就可以了。
-
题目：
这个比较多应该都找得到
-
-
求最长公共前缀（Longest Common Prefix）：
给定两个字符串a,b，有m个询问，每次分别给出两个起始位置x,y，求a串从x开始，b串从y开始的最长公共前缀(LCP)长度；
-
思路
二分+RK Hash
如上文预处理出每个前缀的Hash值，我们就能O(1)内求出子串Hash值，然后不断二分长度L就好了
根据fstqwq的说法，时间复杂度 (O(mlog L))
然而，自己摸索出了一个骚操作(好象又在哪里听过这种做法？),用倍增,因为二分的上下届可能比较大，不如倍增来的快.
-
题目：
--update--
TJOI2017DNA
https://www.luogu.org/problemnew/show/P3763我的题解：https://www.luogu.org/blog/Rye-Catcher/solution-p3763
luogu上搜中文和算法都没有，搜英文有一道CF的题不过要用树链剖分，可惜我现在的知识点不够;
另外我惊人地发现一道JSOI2008火星人的题目和 SP3109 STRLCP - Longest Common Prefix几乎一模一样
-
-