一、BF 算法(Brute Force,暴力匹配)
就是暴力循环查找,虽然复杂度比较高,但是却是经常使用的算法。
第一,实际的软件开发中,大部分情况下,模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候,当中途遇到不能匹配的字符的时候,就可以就停止了,不需要把 m 个字符都比对一下。所以,尽管理论上的最坏情况时间复杂度是 O(n*m),但是,统计意义上,大部分情况下,算法执行效率要比这个高很多。
第二,朴素字符串匹配算法思想简单,代码实现也非常简单。简单意味着不容易出错,如果有 bug 也容易暴露和修复。在工程中,在满足性能要求的前提下,简单是首选。
二、RK算法(Rabin-Karp,n-m+1 ,比较适合已知子串长度的搜索)
在BF算法中,如果模式串长度为 m,主串长度为 n,那在主串中,就会有 n-m+1 个长度为 m 的子串,我们只需要暴力地对比这 n-m+1 个子串与模式串,就可以找出主串与模式串匹配的子串。
举例一:主串、模式串与匹配种类
主串为:{5,4,3,2,1}长度为5,模式串为{1}长度为1,则共有5种匹配
主串为:{5,4,3,2,1}长度为5,模式串为{2,1}长度为2,则共有4种匹配
主串为:{5,4,3,2,1}长度为5,模式串为{3,2,1}长度为3,则共有3种匹配
主串为:{5,4,3,2,1}长度为5,模式串为{4,3,2,1}长度为4,则共有2种匹配
主串长度-模式串长度+1=匹配种类
但是,每次检查主串与子串是否匹配,需要依次比对每个字符,所以 BF 算法的时间复杂度就比较高,是 O(n*m)。我们对朴素的字符串匹配算法稍加改造,引入哈希算法,时间复杂度立刻就会降低。
RK算法的思路是这样的:我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了(这里先不考虑哈希冲突的问题,后面我们会讲到)。因为哈希值是一个数字,数字之间比较是否相等是非常快速的,所以模式串和子串比较的效率就提高了。
用一句话来描述就是,将之前匹配的可能性转换成为哈希值再去比较,因为哈希值是一个数字,数字之间比较的速度快,所以会提升效率。
但是,通过哈希算法计算子串的哈希值的时候,需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了(匹配部分由字符串转换为数字),但是,算法整体的效率并没有提高。
举例二:将字符串通过哈希算法转换为数字(需要设计的很巧妙)
之前的思路是
主串{a,b,c,d,e,f,g,h}长度为8,模式串{c,d,e}长度为3,可以匹配的模式为8-3+1=6种。
将{a,b,c}、{b,c,d}、{c,d,e}、{d,e,f}…{f,g,h}通过哈希算法转换为一组数字,也将模式串转换为数字,进行比较,这样虽然使算法的比较效率提高了,但是算法的整体效率并没有提高。
新的思路
主串{a,b,c,d,e,f,g,h}长度为8,模式串{c,d,e}长度为3,
主串中的字符串只包含 a~z 这 26 个小写字母,那我们就用二十六进制来表示一个字符串。我们把 a~z 这 26 个字符映射到 0~25 这 26 个数字,a 就表示 0,b 就表示 1,以此类推,z 表示 25。
主串{a,b,c,d,e,f,g,h}可以转换为{0,1,2,3,4,5,6,7},模式串{c,d,e}可以转换为{3,4,5}这样对比就快了很多。
举例三:思考题
根据M-N+1得知有九种,再根据哈希算法,可以转换成33的数组。
ca
ef可以转换为c=226,a=02626,e=4262626 ,f=52626262626
三、BM算法(遇到匹配不到的字符,就向后多滑动一些,最优算法,学会可以不学KMP算法,不如这个快。)
BM(Boyer-Moore)算法是一种非常高效的字符串匹配算法,有实验统计,它的性能是著名的KMP 算法的 3 到 4 倍。
一.BM 算法的核心思想
我们把模式串和主串的匹配过程,看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时,BF 算法和 RK 算法的做法是,模式串往后滑动一位,然后从模式串的第一个字符开始重新匹配
在这个例子里,主串中的 c,在模式串中是不存在的,所以,模式串向后滑动的时候,只要 c 与模式串没有重合,肯定无法匹配。所以,我们可以一次性把模式串往后多滑动几位,把模式串移动到 c 的后面。
BM算法,本质上其实就是在寻找这种规律。借助这种规律,在模式串与主串匹配的过程中,当模式串和主串某个字符不匹配的时候,能够跳过一些肯定不会匹配的情况,将模式串往后多滑动几位。
二.BM 算法原理分析(最实用)
1、坏字符规则
在匹配的过程中,我们都是按模式串的下标从小到大的顺序,依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯,而 BM 算法的匹配顺序比较特别,它是按照模式串下标从大到小的顺序,倒着匹配的。
从模式串的末尾往前倒着匹配,当发现某个字符没法匹配的时候,我们把这个没有匹配的字符叫作坏字符(主串中的字符)。
拿坏字符 c 在模式串中查找,发现模式串中并不存在这个字符,也就是说,字符 c 与模式串中的任何字符都不可能匹配。这个时候,我们可以将模式串直接往后滑动三位,将模式串滑动到 c 后面的位置,再从模式串的末尾字符开始比较。
模式串中最后一个字符 d,还是无法跟主串中的 a 匹配,这个时候,还能将模式串往后滑动三位吗?答案是不行的。因为这个时候,坏字符 a 在模式串中是存在的,模式串中下标是 0 的位置也是字符 a。这种情况下,我们可以将模式串往后滑动两位,让两个 a 上下对齐,然后再从模式串的末尾字符开始,重新匹配。
当发生不匹配的时候,我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在,我们把这个坏字符在模式串中的下标记作 xi。如果不存在,我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。
自己组织一下
BM算法坏字符规则指的是,一个长度为L的字符串,通常的做法是从0开始去匹配,BM算法的方式是从字符串的尾部进行匹配,如果匹配的元素相同,则去匹配末尾-1的元素。
如果匹配的元素不同,判断该元素是否在长度为L的字符串内,如果不在则向后挪L长的,如果在,则标记第一个相同的元素,并移动对应的距离。
2、好后缀规则
好后缀规则实际上跟坏字符规则的思路很类似。
这个其实和坏字符的思路比较类似,主要是为了避免坏字符规则导致模式串向后漂移。
如果匹配到了一个字符串,如bc,但是bc的后面又出现了坏字符,将bc标记出来,在模式串中去寻找另一个和bc相匹配的字符串,如果找到了,就将找到的字符串的位置滑动到该位置。如果没找到,直接将模式串,滑动到主串中bc(标记的字符串)的后面,因为之前的任何一次往后滑动,都没有匹配主串中bc的情况。
找到了
没找到
当模式串和主串中的某个字符不匹配的时候,如何选择用好后缀规则还是坏字符规则,来计算模式串往后滑动的位数?我们可以分别计算好后缀和坏字符往后滑动的位数,然后取两个数中最大的,作为模式串往后滑动的位数。这种处理方法还可以避免我们前面提到的,根据坏字符规则,计算得到的往后滑动的位数,有可能是负数的情况。
3、BM算法代码实现
1.大佬写的
// 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;
}
2.自己写的
在这里插入代码片
四、KMP算法(核心思想,利用已匹配字符串)
KMP算法和BM算法在思路上有一些类似,区别点在于
1、 KMP算法是从左往右进行匹配,BM算法是从右往左进行匹配;
2、 KMP算法是根据匹配表长度进行滑动,而BM算法是根据好后缀(好后缀类似于KMP算法)和坏字符规则进行滑动;
3、 BM算法比KMP算法要快好几倍,因此KMP算法其实不是很实用;
原文中讲的很是晦涩,其实理解上来讲不是很难。
重点在于理解什么叫部分匹配表
部分匹配表
参考文章:https://blog.csdn.net/paincupid/article/details/81159320
从左到右进行匹配,如果第一位就不想等,则进行滑动到与第一位字符相等的位置。
已经滑动到与第1-6字符相等,但是第七位不相等的位置。
在KMP算法中,要对这些已经匹配的数据进行利用
已经匹配的字符为ABCDAB,针对已经匹配了的信息进行计算,得出部分匹配值。
ABCDAB可以从前和后分别截取,可以分为
前缀:A,AB,ABC,ABCD,ABCDA
后缀:B,AB,DAB,CDAB,BCDAB
其中相匹配的字符串是AB,长度为2。
ABCDAB的长度为6,因此向右滑动四位。
滑动后得到上图,进行匹配,只有AB为已匹配字符,后缀和前缀的匹配值是0,AB的长度是2
因此向右再次滑动2位。
A与空不匹配,向右滑动至首字母相等的位置
长度为6,匹配长度为2,滑动4
完成匹配。
版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: