本文主要讲述了串的模式匹配算法，包括BF算法、RK算法、KMP算法、BM算法，使用不同的算法实现目标串查找子串，重点在于分析的过程，通过不同的算法分析提高逻辑思维能力
模式匹配的目的就是在目标串中查找与模式串相等的子串。在这里称呼主串为s，模式串为t，主串的长度为n，模式串的长度为m
(BF)Brute-Force算法
介绍：
暴力算法，将目标串和模式串的每个字符都进行一一比较。性能最差，但是使用最广，因为实现简单，而且在字符串较小的情况下耗费的性能也很小。
核心思想
- 将长度为n的目标串分成长度为n-m个子串
- 在一轮比较中，如果模式串的每个字符与其中的某个子串的所有字符相匹配，则查找到该子串
实现思路
- 目标串的第一个字符与模式串的第一个字符进行比较
- 如果成功了，就用目标串的第二个字符与模式串的第二个字符进行比较
- 如果失败了，就对主串进行回溯，回溯到起始位置的下一个位置继续按照上面的方式进行比较，同时比较的模式串仍然是从第一个字符开始
代码实现
#define NOT_FOUND -1
int findStringInString(char *a, char *b) {
if (!*a || !*b) return NOT_FOUND;
int i = 0, j;
char *p;
while (a[i]) {
if (a[i] == b[0]) {
p = a + i; // 当前字符串的开头
j = 1; // 头已经比较过了，从下一个位置开始比较
while (p[j] && b[j] && p[j] == b[j]) // 一次比较
j++;
if (!b[j]) // 子串完全匹配
return i;
if (!p[j]) // 主串已经到末尾了，之后字符串长度都不够，就不需要再比较了
return NOT_FOUND;
}
i++; // 移动字符开始的索引
}
return NOT_FOUND;
}
算法分析
O(n*m)
RK算法
介绍：
RK算法把字符串比较问题，转换为了Hash值比较问题。
将模式串t的每个字符的比较改成了将串作为整体与目标串进行哈希值比较，这样就减少了比较次数
以前模式串与子串的比较需要比较每个字符，现在只要整体比较依次哈希值就可以。所以减少了比较次数。
核心思想
- 将模式串t的每个字符串与目标串的比较转化为模式串整体的哈希值与目标串的比较
- 减少模式串中单个字符的比较次数
算法说明
- 计算得到模式串的哈希值，再分别计算目标串中的各子串哈希值，依次进行比较
- 重点在于哈希值的计算
- 利用前一个Hash值计算结果，辅助计算下一个Hash值。(可以算是动态规划)
- 先计算第一个哈希值，后面的就可以省略掉中间部分字符的计算，只减去第一个字符，再加上第二个字符
- 在比较的过程中，进行判断，同时解决Hash冲突问题。
哈希算法
- 将26个字母以10进制数的样式来表示，计算得到其哈希值
- 比如'a'的ASC码为97，如果直接用，很容易造成溢出问题，所以在计算Hash值时会减去'a'。
- 比如"abc"就可以被表示为：
哈希算法.png
这里我们可以发现一个Hash冲突问题，比如"abc"和"bc"的Hash值是一样的，因为最高位是0。所以还需要进行哈希冲突算法。
哈希冲突算法：
- 发生冲突时，根据字符的起点，比较所在目标串的子串与模式串的所有字符
利用前一个结果计算下一个哈希值
这是因为目标串的相邻子串，其实相差的只有第一个字符和最后一个字符，其他字符是相同的，
所以我们可以利用前一个计算结果减去前一个字符串的第一个字符串，加上这个字符串的最后一个字符就够了。
代码实现
#define NOT_FOUND -1
bool isMatch(char *mainStr, int i, char *matchStr, int m) {
for (int j = 0; j < m; j++) {
if (mainStr[i+j] != matchStr[j])
return false;
}
return true;
}
int RK(char *mainStr, char *matchStr) {
int d = 26; // 表示进制
int n = (int)strlen(mainStr); // 主串长度
int m = (int)strlen(matchStr); // 子串长度
unsigned int mainHash = 0; // 主串分解子串的哈希值
unsigned int matchHash = 0; // 模式串的哈希值
// 1.求得子串与主串中0~m字符串的哈希值[计算子串与主串0-m的哈希值]
// 循环[0,m)获取模式串A的HashValue以及主串第一个[0,m)的HashValue
int offset = 'a' - 1; // a为最小值，保证a是最高位时，不会为0
// 2.计算哈希值同时获取d^m-1值(因为经常要用d^m-1进制值)
int dm1 = 0;
for (int i = 0; i < m; i++) { // 小于m，不计算\0的值，数字会小一点
matchHash = (d * matchHash + (matchStr[i] - offset));
mainHash = (d * mainHash + (mainStr[i] - offset));
dm1 = dm1 > 0 ? dm1 * d : 1;
}
// 3.遍历比较哈希值
for (int i = 0; i <= n-m; i++) {
if (matchHash == mainHash // 判断模式串哈希值是否和其他子串的哈希值一致
&& isMatch(mainStr, i, matchStr, m)) // 哈希值相等后，再次用字符串进行比较，防止哈希值冲突
return i;
// 计算下一个子串的哈希值
mainHash = (mainHash - (mainStr[i] - offset) * dm1) * d + mainStr[i+m] - offset;
// mainHash = (mainHash % dm1) * d + mainStr[i+m] - offset; // 或者取余
}
return NOT_FOUND;
}
算法分析
- 理想情况下是O(n)
- 最差情况下是O(n*m)，也就是每次比较都会冲突
KMP算法
介绍：
针对BF的弊端，在KMP算法中可以进行多字符的跳跃对比，以此来避免目标串的不必要回溯。
例子：
例子.png
- 在这个例子中，目标串中的c在模式串是不存在的，肯定无法匹配，所以模式串向后移动时就没必要再比较c了，
- 而是直接可以跳过c比较下一个字符。
- 我们可以跳跃到下一个有a的地方，这里就需要KMP算法
简单说明一下：
- 在目标串中有多个子串，模式串在与目标串进行比较时，前面的几轮虽然失败了，但是会得到一个信息就是成功的几个字符串样式，我们可以使用这个信息来供后续的查找。
- 接下来在使用子串时，先使用刚才拿到的信息来判断，是否一致，如果不一致，就直接跳跃到下一个子串再比较。
- 通过目标串的子串不停的跳跃就避免了目标串的不必要回溯。
- 因此这个算法的重点在于模式串需要在目标串跳跃几个位置，而这个跳跃字符数量是通过模式串的真子串来计算得到的
核心思想
- 进行多字符的跳跃对比，跳跃到下一个已经匹配过的字符串的重复字符串的后面，这些字符不需要重复匹配，就可以直接从这个后面的字符进行匹配
- 可以通过模式串的真子串判断目标串的下一个已经匹配过的字符串是在什么位置
- 有两个步骤，先获取模式串的真子串，后进行匹配跳跃
真子串：
- 模式串中的重复子串就是真子串，并且这里的部分匹配肯定要与模式串的开头字符相匹配
- 这里的真子串的大小也就是匹配数组的值
- 所比较的第一个子串是以模式串起始字符串作为开头的串
- 这里得到了模式串中的两个相同的子串，在回溯时就不需要比较上一个子串，而直接比较下一个字符串
- 如果有多个真子串，就取最长的真子串
匹配：
- 若当前位置不匹配，当前位置前存在重复子串，则通过回溯可以跳过重复的子串继续匹配，而不是从头开始。
- 在某一位置不匹配，在此位置前存在包含真子串，就回溯到真子串所在的下一个字符进行比较，而不必再比较真子串
- 模式串与目标串的匹配过程中，如果出现不匹配字符，此时查看其next[j]不为0，也就是有真子串的存在,而这个真子串的长度就是next[j]
- 这样就不需要将目标串回溯到起始位置，而是直接回溯到next[j]个位置
例如：目标串："abxabcabcaby"，模式串："abcaby"
KMP的算法示意图.png
模式串的最大真子串为ab,
我们在匹配时，发现目标串的子串abcabc与模式串的前字符都匹配，最后一个字符不匹配
所以就从目标串的abcabc的后面abc开始与模式串进行匹配，而不需要匹配前面的abc了。
也就是从上一个a字符直接跳跃到了下一个a字符，而不是从b字符开始。
改进：
会存在一种情况：
- 我们定义next[j]=k，但是出现Tj=Tk，也就是说next[j]=next[k]
- 这就说明还需要在Tk的基础上获取真子串长度，也就是next[k]
实现思想：
- 也就是说此时在找Tj的时候应该在j的前面的真子串的前面继续找真子串
- 此时的值next[j]=next[next[j]]
- 需要将next[j]修正为nextval[j]，也就是在一次真子串查找后再查找一次
BM算法
介绍：
它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP算法的三四倍。BM算法的原理很多复杂，比较难懂，学起来比较烧脑。
实现思想和KMP算法基本上是一样的，都是先计算模式串的真子串，之后再查找真子串的大小，当出现不匹配时，直接在真子串后进行匹配，区别于KMP算法，它是从后往前匹配的
这里比上面的KMP算法增加了一个坏字符规则，可以更快的跳跃，当然KMP算法本身也可以使用坏字符规则
匹配顺序.png
核心思想
跳跃位置计算
坏字符规则
- 当目标串与模式串发生不匹配时的那个目标串中的字符就是坏字符
- 创建一个坏字符数组，将所有的字符存入到数组中，并且记录字符在模式串中所在的最右侧下标，如果不存在，就记为-1
- 跳跃大小就为si-xi
- si是发生不匹配时坏字符对应模式串中的字符下标
- xi就是坏字符在模式串中的最右侧的下标
坏字符规则.png
说明：
- 上图可以看到，坏字符c在模式串中不存在，直接跳跃模式串个大小的距离
- 再次匹配发现坏字符为a，在坏字符数组中查知为最右侧下标为2，所以直接跳跃2个位置。
好后缀规则
- 好后缀规则就和上面所分析的KMP算法一样，只是他是从后往前比较的，所以此处是后缀子串，也就是包含了最后一位字符
- 在模式串中如果有后缀子串的重复子串，就将对应的这个重复子串移动到此处对应
好后缀规则.png
总结
- BF算法是将模式串的每个字符都与目标串进行比较，并且如果不匹配，会移动到目标串的下一个字符继续比较，所以算法复杂度是O(n*m)
- RK算法是将模式串作为一个哈希值与目标串的相应字符数量的哈希值进行比较，并且如果不匹配，会移动到目标串的下一个字符继续比较（需考虑哈希冲突），所以算法复杂度是O(m)
- BM算法和KMP算法都是将为了目标串不需要回溯，避免相同真子串的重复比较，依次减少字符串的匹配，算法复杂度最好情况下为O(n/m)
- BM算法和KMP算法的区别就是BM是后缀匹配，KMP算法是前缀匹配，其核心原理是一样的，只是比较的顺序不一样
网友评论