一、BF算法
BF算法中的BF是Brute Force的缩写，可以叫暴力算法，也叫朴素匹配算法。这种算法的字符串匹配很“暴力”，比较简单、容易理解，但性能也不高。
BF算法的原理就是，在主串中，检查起始位置分别是0、1、2...n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。如下图
实现代码如下：
/**
* BF算法
*
* @param mainStr 主串
* @param pattStr 模式串
* @return 模式串在主串的起始位置
*/
public int bruteForce(String mainStr, String pattStr) {
int n = mainStr.length();
int m = pattStr.length();
int i = 0;
while (i <= n - m) {
int j = 0;
while (j < m && mainStr.charAt(i + j) == pattStr.charAt(j)) {
// 模式串全部匹配上
if (++j == m) {
return i;
}
}
// 没有匹配上，主串向后移一步
i++;
}
return -1;
}
我们从代码可以看出，有两个循环，m要比n小，外循环的循环次数不超n ,内循环次数为m,所以整个时间复杂度O(n*m)
二、RK算法
RK算法的全称叫Rabin-Karp算法，是Rabin和Karp发明的。它是BF算法的升级版。
在BF算法中，每一次检查主串，都要依次比对每个字符，所以算法的时间复杂度比较高。
在RK算法中，我们引入哈希算法，对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（如果发生哈希冲突，再比较子串与模式串每个字符是否相等）。
代码实现如下:
/**
* RK算法
*
* @param mainStr 主串
* @param pattStr 模式串
* @return 模式串在主串的起始位置
*/
public int rabinKarp(String mainStr, String pattStr) {
int n = mainStr.length();
int m = pattStr.length();
// 计算模式串哈希值
int pattHash = 0;
for (int i = 0; i < m; i++) {
pattHash += pattStr.charAt(i);
}
int mainHash = 0;
int i = 0;
while (i <= n - m) {
// 当i=0时，计算子串从0开始的哈希值，这里我们用比较简单的哈希算法，直接用字符的ASCII码值作为哈希值
if (i == 0) {
for (int j = 0; j < m; j++) {
mainHash += mainStr.charAt(j);
}
} else {
// 当i!=0，子串i位置开始的哈希值 = (子串 i-1位置开始的哈希值 )- (i-1位置字符的哈希值) + (i 位置字符的哈希值)
mainHash = mainHash - mainStr.charAt(i - 1) + mainStr.charAt(i);
}
// 子串和模式串的哈希值相等，说明找到位置了
if (mainHash == pattHash) {
// 防止哈希冲突，再比较一下
int j = 0;
while (j < m && mainStr.charAt(i + j) == pattStr.charAt(j)) {
j++;
}
if (j == m) {
return i;
}
}
i++;
}
return -1;
}
我们看看RK算法的时间复杂度是多少呢？
只需要扫描一遍主串就能计算出所有子串的哈希值，模式串哈希值与每个子串之间的比较的时间复杂度是O(1)，所以RK算法整体的时间复杂度就是O(n)，这里是没有考虑到哈希冲突情况下的；在极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串，那时间复杂度就会退化成O(n*m)；但一般情况下，冲突不会很多。
三、BM算法
BM算法包括两个部分，分别是坏字符规则（bad character rule）和好后缀规则(good suffix)
1.坏字符规则
把模式串的末尾往前倒着匹配，当发现某个字符没法匹配，那么就把这个没有匹配的字符叫作坏字符（主串中的字符）
拿到坏字符，我们要这时要判断模式串要移动几位，再继续跟主串比对。这里有两种情况;
第一种情况，坏字符在模式串中不存在，假如坏字符所在的位置对应模式串位置为 j，直接往后移动 j +1 位，如下图
第二种情况，坏字符在模式串中存在，假如坏字符所在的位置对应模式串位置为 j，坏字符找到在模式串中最靠后的字符位置为k,那么模式串往后移动 j-k 位，如下图
具体实现代码如下：
/**
* BM算法 - 坏字符规则
*
* @param mainStr 主串
* @param pattStr 模式串
* @return 模式串在主串中位置
*/
public int badSuffix(String mainStr, String pattStr) {
int n = mainStr.length();
int m = pattStr.length();
// 记录模式串字符最后的位置，为了计算要移动的位置
int[] bc = new int[256];
for (int i = 0; i < 256; i++) {
bc[i] = -1;
}
for (int i = 0; i < m; i++) {
bc[pattStr.charAt(i)] = i;
}
// 记录主串的位置
int i = 0;
while (i <= n - m) {
int j = m - 1;
while (j >= 0 && mainStr.charAt(i + j) == pattStr.charAt(j)) {
// 都匹配上了，返回 i 的位置
if (--j == -1) {
return i;
}
}
// 没有匹配上,判断是否坏字符在模式中的位置，不存在则为-1;
i = i + j - bc[mainStr.charAt(i + j)];
}
return -1;
}
这里要说明一点，为什么记录模式串字符最后的位置，如果坏字符在模式串里多处出现，在计算要移动的位置的时候 ，选择最靠后的那个，这样不会让模式串移动过多，导致本来可能匹配的情况被移动略过。
要注意坏字符规则是会出现有bug情况，比如 主串为dddddddd, 模式串为addd，这个情况下，会导致 j-k 为负数，咱们来算一算，坏字符为d, 对应的模式串下标为0，pattPos[d] = 3, 那么 0 -3 = -3; 所以BM算法还需要用到 “好后缀规则”
2.好后缀规则
好后缀规则与坏字符规则的思路其实很类似，也是找到坏字符的位置，然后坏字符对应模式串的位置后面就是已经匹配上的字符，那么这些字符就是好后缀。
好后缀规则有三种情况：
第一种情况，好后缀在模式串能匹配上，把模式串移动到好后缀匹配上的位置，如下图，我们可以分析：如果好后缀的长度为k，根据这个长度获取这个后缀的共同后缀的下标x，可以计算m的值，我们用一个数组 suffix 代表模式串不同长度的后缀的共同后缀的起始下标；j代表坏字符的下标，那么可以得到一个计算公式 m = j - suffix[k] + 1，把下图的值代入可以计算 m = 4 - 1 + 1 = 4。
第二种情况，好台缀在模式串上不能匹配上，但是好后缀的子串可以匹配上模式串的前缀子串，这时需要把模式串移动到前缀子串匹配上好后缀的子串的位置上，这里看图会更好理解；我们来分析如何来计算m的值：我们用一个数组 prefix 代表模式串不同长度的后缀是否有匹配上的前缀；如果好后缀子串匹配上的长度为k，模式串的长度为len；当 prefix[k] = true, 那 m = len - k;
第三种情况，好后缀在模式串不能匹配上，并且好后缀的子串匹配不上模式串的前缀子串，这时直接移动模式串的好后缀的后一位子，如下图，如果模式串的长度为len，很简单的得出 m = len;
根据上面的三种情况，我们需要计算 suffix数组 和 prefix数组，如下图
代码实现如下：
/**
* 计算 suffix数组和 prefix数组
* @param pattStr 模式串
* @param m 模式串长度
* @param suffix 公共后缀子串不同长度的起始下标数组
* @param prefix 公共后缀子串是是否有匹配上前缀子串数组
*/
private void generateGS(String pattStr, int m, int[] suffix, boolean[] prefix) {
// 设置初始值
for (int i = 0; i < m; i++) {
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; i++) {
int j = i;
// 公共后缀子串长度
int k =0;
// 不同长度下比较字符是否相等，并且记录最靠后公共后缀子串的起始下标
while (j >= 0 && pattStr.charAt(j) == pattStr.charAt(m - 1 - k)) {
--j;
suffix[++k] = j + 1;
}
// 如果公共后缀子串也是模式串的前缀子串
if (j == -1) {
prefix[k] = true;
}
}
}
BM算法完整代码如下：
/**
* Boyer Moore 算法 - 坏字符规则和好后缀结合
*
* @param mainStr 主串
* @param pattStr 模式串
* @return
*/
public int bm(String mainStr, String pattStr) {
int n = mainStr.length();
int m = pattStr.length();
// 模式串的每个字符出现的最后位置
int[] bc = new int[SIZE];
generateBC(pattStr, m, bc);
// 模式串不同长度的后缀的最靠后共同后缀的起始位置 eg: abbcdb 长度为1的后缀b,的最靠后共同后缀的起始位置为2
int[] suffix = new int[m];
// 模式串不同长度的最靠后共同后缀是模式串相同长度的前缀 eg: abbcdab 长度为2的后缀ab,
// 模式串相同长度的前缀为ab,两者相同true;
boolean[] prefix = new boolean[m];
// 给两个数组赋值
generateGS(pattStr, m, suffix, prefix);
// 开始对比找位置
int i = m - 1;
while (i < n) {
int j = m - 1;
// 从模式串的最后往前比
while (j >= 0 && mainStr.charAt(i) == pattStr.charAt(j)) {
--i;
// 两个相同，继续往前,直到模式串的起始位位置都相同，说明找到了
if (--j == -1) {
return i + 1;
}
}
// 如果没有找到，此时 i+j 的位置就是坏字符。
// 根据坏字符规则计算 i 需要移动几个位置
int b = j - bc[mainStr.charAt(i)];
int g = 0;
// 如果有好后缀,则根据好后缀规则计算
if (j < m - 1) {
// 好后缀规则计算
g = getGoodSuffix(j, m, suffix, prefix);
}
// 规则移动的多，就用哪个
i += Math.max(b, g);
}
return -1;
}
// j 代表坏字符在模式串的位置，m代表模式串长度
private int getGoodSuffix(int j, int m, int[] suffix, boolean[] prefix) {
// 计算好后缀的长度 eg： minaStr=hacdgcabcd pattStr= abcd,
// 第一次对比的坏字符是a对应的位置是1,好后缀是cd,它长度就是 (4-1)-1=2;
int l = m - j - 1;
// 第一种情况，如果好后缀在模式串中有共同后缀，将模式串移动至好后缀匹配的位置
if (suffix[l] != -1) {
return j - suffix[l] + 1;
}
// 第二种情况，好后缀不在模式串，好后缀的后缀子串和模式串的前缀有重合的部分，将模式串移动到好后缀的后缀子串重合的位置。
for (int i = l - 1; i >= 1; i--) {
if (prefix[i]) {
return m - i;
}
}
// 第三种情况，好后缀不在模式串，好后缀的后缀子串和模式串的前缀没有重合的部分,将模式串移动到好后缀的后一位。
return m;
}
private static final int SIZE = 256;
// 记录模式串的每个字符最靠后的位置
public void generateBC(String b, int m, int[] bc) {
for (int i = 0; i < SIZE; i++) {
bc[i] = -1;
}
for (int i = 0; i < m; i++) {
bc[b.charAt(i)] = i;
}
}
