字符串上
1.开篇问题
如何用哈西实现高效字符串匹配，字符串查找函数，比如 Java 中的 indexOf()，Python 中的 find() 函数等，它们底层就是依赖接下来要讲的字符串匹配算法，简单的两种算法BF，PK
2.BF暴力匹配算法
暴力匹配，在主串n中用模式串m匹配，主串i依次遍历，每个i都有模式串遍历m次，即时间复杂度o(m*n)
i.时间复杂度高但实际开发中常用
第一，虽然BF算法时间复杂度高，但非常简单直接，简单意味着不易出错
第二，对于大多数情况下，主串模式串都不长时，模式串对比主串遇到不符合字符就停止，没必要全部遍历模式串，所以实际时间复杂度低于o(m*n)
3.RK算法(BF改进版)
i.算法思路
主串不必全部遍历，实际只需要遍历主串中n-m+1个子串，与模式串匹配就行。这个不是大改进，实际上引入哈西算法，将n-m+1个子串进行求一个唯一的哈西值，然后和模式串哈西值对比既可，同则找到，不同则无
注:哈西算法求唯一值，非常类似数学中令成t，任何文件图片子串都可以隐射成唯一哈西值
ii.巧妙的哈西算法设计
进制设置:假设要匹配的字符串的字符集中只包含 K 个字符，用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。比如字符串中只包含 a～z 这 26 个小写字符，我们用二十六进制来表示一个字符串，对应的哈希值就是二十六进制数转化成十进制的结果。
注:a-z可简单表示0-25，或者减少冲突a-z表示从小到大的素数，这样更好，至于不可减少的冲突，可以直接对比这个子串和模式串判等就行
查表数组: 26^(m-1) 这部分的计算，可以通过查表的方法来提高效率。事先计算好 26^0、26^1、26^2……26^(m-1)，并且存储在一个长度为 m 的数组中，公式中的“次方”就对应数组的下标。
iii.时间复杂度
查找o(1)但子串n-m+1所以时间复杂度逼近o(n)
只在极端情况下退化成暴力匹配o(n*m)
4.课后思考题
以上所讲都是一维字符串匹配，若是二维字符矩阵，和模式矩阵如何匹配呢？
解:在主矩阵中查找子矩阵，将子矩阵和模式矩阵对比，可以用RK算法，这样时间复杂度等于子矩阵个数(M-m+1)*(N-n+1)
字符串中
1.开篇问题
如何实现文本编辑器中的查找功能？我们在word中查找一个单词，把一个单词替换成另一个就是用的BM算法，今天来学BM（Boyer-Moore）算法。
解:BF在极端情况下退化严重(不高效也退化严重)，RK设计一个可应对各种字符的哈西算法不容易(带特殊符号)，对于工业级软件，高效且极端情况下退化不严重，BM算法就出来了，是KMP算法3-4倍
2.BM算法
i.核心思想
BG，RP算法都是一次一个匹配移动，但BM算法是一次滑动多个移动(跳过肯定不可能匹配的情况)
注:注意这个跳和滑的动作，这表示在模式串中匹配最好是逆序匹配，不顺序匹配，因为越在尾巴的指针越方便滑动，啊！
ii.原理分析
第一，坏字符原则
模式串逆袭匹配时，当发生不匹配的时候，把子串坏字符对应的模式串中的字符下标记作 si(模式串坏字符的后坐标)。
如果坏字符在模式串中存在，把这个坏字符在模式串中的下标记作 xi(模式串坏字符中的前坐标)。如果不存在，把 xi 记作 -1。
那模式串往后移动的位数就等于 si-xi(移动个数=模式串后坏指针-模式串前坏指针)
注:单用坏字符不够，因为si-xi可能出现负数
第二，好后缀原则
跟坏字符原则一致，只是匹配的是模式串和子串重复的串，也是逆序查找
注:分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。避免了坏字符出现负数情况
iii.代码
这两种原则都涉及到在模式串查找子串的坏字符位置，遍历比较低效，一个散列表数组即可快速解决，一种最简单的情况，假设字符串的字符集不是很大，每个字符长度是 1 字节，用大小为 256 的数组，来记录每个字符在模式串中出现的位置。数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置
模式串字符和位置散列表如下:
private static final int SIZE = 256; // 全局变量或成员变量
private void generateBC(char[] b, int m, int[] bc) {
for (int i = 0; i < SIZE; ++i) {
bc[i] = -1; // 初始化 bc
}
for (int i = 0; i < m; ++i) {
int ascii = (int)b[i]; // 计算 b[i] 的 ASCII 值
bc[ascii] = i;
}
}
BM算法代码如下:
// a,b 表示主串和模式串；n，m 表示主串和模式串的长度。
public int bm(char[] a, int n, char[] b, int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int[] suffix = new int[m];
boolean[] prefix = new boolean[m];
generateGS(b, m, suffix, prefix);
int i = 0; // j 表示主串与模式串匹配的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
}
int x = j - bc[(int)a[i+j]];
int y = 0;
if (j < m-1) { // 如果有好后缀的话
y = moveByGS(j, m, suffix, prefix);
}
i = i + Math.max(x, y);
}
return -1;
}
// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
int k = m - 1 - j; // 好后缀长度
if (suffix[k] != -1) return j - suffix[k] +1;
for (int r = j+2; r <= m-1; ++r) {
if (prefix[m-r] == true) {
return r;
}
}
return m;
}
