2018-12-05觉得今天的hash算法真是巧妙 4 113
2018-12-06RK算法，在对主串构建的时候，就对比是不是一样的，一样就不继续计算后面的hash，这样会不会更快一点作者回复: 你说的很对 代码实现就是这样处理的
1 71
2018-12-05思考题：
假设二维主串和模式串的维度分别是 m*n 和 i*j，横向在[0, m-i]，纵向在[0, n-j]取起始点，然后取同样的子串窗口对比，共有(m-i+1)*(n-j+1)个子串。
ps：
文中计算子串哈希值h[i]的公式中，第二个h[i-1]和后面的h[i+m-1]，应该是主串中的第i-1个和第i+m-1个字符的哈希值… 22
2018-12-05思考题：
以模式串矩阵的大小，去匹配主串矩阵，每个小矩阵可以构建成字符串，就能用 RK 算法做字符串匹配了。
如果主串的大小是 M * N，模式串大小为 m * n，则时间复杂度为 (M - m + 1) * (N - n + 1)。 1 18
2019-01-27看了很多评论后，发现思考题其实就是举一反三，我们可以在比较时，将二维串矩阵看作是字符串来处理，至于怎么转换成一维字符串，应该有很多方法，比如子串矩阵和模式串矩阵都用同样的规则来组成一个字符串，从左到右，再从上到下遍历取矩阵的元素a[i][j]。转换为一维字符后，就可以用BF或者RK算法了 。
复杂度分析，假设二维主串矩阵和模式串矩阵的维度分别是 m*n 和 i*j，按一个个矩阵来看子串的话，共有(m-i+1) * (n-j+1)个子串矩阵。
用RK算法的话，复杂度就是O((m-i+1) * (n-j+1))。 2 12
2018-12-05h[i] = 26*(h[i-1]-26^(m-1)*h[i-1]) + h[i+m-1];
其中, h[i]、h[i-1] 分别对应 s[i] 和 s[i-1] 两个子串的哈希值
------------------
文中这个公式，26*(h[i-1]-26^(m-1)*h[i-1])可以化简为26*h[i-1]*(1-26^(m-1))，所以这里是不是应该改为26*(h[i-1]-26^(m-1)*s[i-1])，用s[i-1]代表当前位置的字符串的值，例如图中d的值是3，同样的公式后面加 h[i+m-1]是不是也是s[i+m-1]呢展开作者回复: 写错了 感谢指正 已经改了
1 10
2018-12-05老师，前天面试被问到一个问题，关于地图算法的，比如线路推荐。请问地图算法会讲到么作者回复: 在高级篇那部分会涉及一点
1 9
2019-01-09老师您应该把公式的推理过程简单地说一下，这公式对您来说非常简单，但是对于我这种基础差的人，完全是懵逼的状态。看着大家讨论，却无法深入下去。/(ㄒoㄒ)/~~作者回复: 我补一下
7
2018-12-05以前刷题的时候，遇到过rk算法，当时是没太考虑hash冲突，一个字母对应一个数字，子串的hash值就是子串中的字母对应的数字想加。
今天大佬将之抽象提炼出来，还专门提到冲突解决方法，不可谓不妙！ 7
2018-12-12好几期没看了，感觉跟不上了作者回复: 不着急 慢慢来 没必要一直紧跟着
6
2018-12-05二维矩阵只要如果以i'j为左上角，即可定义一个i.j i+1.j i. j+1 i+1.j+1的子串，其本质是和字符串相同的，即可以由rf又可以由bf解 6
2018-12-07RK算法和布隆过滤器的思想是一致的 5
2018-12-05“h[i] = 26*(h[i-1]-26^(m-1)*h[i-1]) + h[i+m-1];其中, h[i]、h[i-1] 分别对应 s[i] 和 s[i-1] 两个子串的哈希值。”老师你好，26^(m-1)*h[i-1]中的h[i-1]和h[i+m-1]应该是一个字符的哈希值而不应该是子串的哈希值吧？？PS：用您的例子套用公式：h0 = 3*26*26+1*26+2 = 2056；h1=26*(h0-26*26*h0)+(4*26*26+3*26+4) = -36080014 和期望的哈希值1*26*26+2*26+4=732不符。 1 5- 2018-12-05思考题:
可以先查找第一行的字符串，假设长度为m，用bf或者rk都可以，假设是n*n的数组，
bf的复杂度是(n-m)*n
rk的复杂度为n
如果有匹配，则依次匹配第2到m行字符串。每次的复杂度与第一次的相同
最坏时间复杂度为
bf:(m-n)^2*n^2
rk:n^2
但是如果第一行不匹配的话是不会进行第二行的匹配的，平均复杂度会小很多。展开 5 
2019-03-01RK算法有两个可以改进的点，一个可以避免hash冲突，另一个可以减少hash计算次数。
改进一：先计算模式串的hash值，记录下来，然后计算每一个子串的hash，计算一次，就对比一次，如果hash值匹配，在全量对比字符串。这样做可以不用关心hash冲突问题。
改进二：计算子串hash值的时候只要计算到n-（n-m）处即可，剩下的子串长度小于模式串，不用计算。 4- 2019-01-09h[i] = 26*(h[i-1]-26^(m-1)*(s[i-1]-'a')) + (s[i+m-1]-'a');
其中, h[i]、h[i-1] 分别对应 s[i] 和 s[i-1] 两个子串的哈希值
好吧，这一段代码我对照上下文看了10遍，看懂了。我承认我很蠢作者回复: 抱歉 没写清楚
4 
2018-12-06基于BF的匹配算法平时的用的比较多，看完之后想了一会觉得没有什么情况会用到第二种RK算法的情况，因为平时业务关系可能没有做到相关的项目，所以想问老师一般什么场景会使用RK这种匹配算法呢？作者回复: 应该是比较刁钻的场景 我也没遇到过 平时都是直接用编程语言提供的函数。不过不耽误我们学习他的思想 技巧
4
2018-12-31RK 算法，计算相邻两个子串哈希值的规律，比如，相邻两个子串分别为 "dbc" 和 "bce"，那么 s[i-1] = 'd'，s[i]='b' ，与 'a' 相减意思是，它们的 ASCII 码值的差值正好表示字母的数值；
评论中有同学不明白老师给的哈希值 h[i] 和 h[i-1] 之间的关系，我想应该是 s[i] 和 s[i-1] 代表什么这点没明白。 3
2018-12-05思考题二维数组用RK算法计算哈希值要复杂一些，i-1 j-1不越界的情况下，如果模式串的行数大于列数可以通过h[i-1,j]计算h[i,j]，如果列数大于行数可以通过h[i,j-1]计算h[i,j] 还有更好的方法计算哈希值吗？
另外正文里的计算哈希值的公式貌似写错了，应该是
h[i] = 26*(h[i-1]-26^(m-1)*(s[i-1]-‘a’)) + (s[i+m-1]-‘a’); 3
2019-07-08字符串匹配算法分类：单模式串匹配算法&多模式串匹配算法
BF算法时间复杂度：o(m * n)
BF算法空间复杂度：o(1)
BF算法在jdk中的实践：String的indexof
BF算法优点：大部分实践情况下模式串和主串都不太长，且经常遇到能剪枝的情况，实际算法执行效率要比o(m * n)要好；符合KISS原则
RK算法时间复杂度：o(n)
RK算法空间复杂度：o(m)
RK算法中获得的启发：
1. 算法调优的核心就是减少无用功
2. 哈希表经常作为用空间换时间的典型数据结构
3. 当前算法的进行要考量是否能复用之前的结果，即考量步骤的前后关联性（可能有点动态规划的意思）展开 2