建网站 开发app,如何给网站做备份,三只松鼠口碑营销案例,wordpress 菜单 双语字符串匹配算法是在实际工程中经常遇到的问题#xff0c;也是各大公司笔试面试的常考题目#xff0c;本文主要介绍BF算法#xff08;最好想到的算法#xff0c;也最好实现#xff09;和KMP算法#xff08;最经典的#xff09;
一、BF算法 BF算法#xff0c;即暴力(Bru…字符串匹配算法是在实际工程中经常遇到的问题也是各大公司笔试面试的常考题目本文主要介绍BF算法最好想到的算法也最好实现和KMP算法最经典的
一、BF算法 BF算法即暴力(Brute Force)算法是普通的模式匹配算法BF算法的思想就是将目标S的第一个字符与模式串T的第一个字符进行匹配若相等则继续比较S的第二个字符和T的第二个字符若不相等则比较S的第二个字符和T的第一个字符依次比较下去直到得出最后的匹配结果。BF算法是一种蛮力法。 ---这段话来自百度百科 这段话晦涩难懂需要例子支持。
下面我们就通过例子来解释这个问题。 l假定我们给出字符串“ababcabccabcacbab”作为主串然后给出子串:“abcac”现在我们需要查找子串是否在主串中出现出现返回主串中的第一个匹配的下标失败返回-1;
1.图解 2.代码实现 思路 分别用 i 和 j 来遍历 主串 和 子串 当主串和子串字符相同 i j 不同时 i i - j 1 i从下一个i开始继续遍历 j 0子串回到开头 直到 j lenSub (子串遍历完了 返回 i - j 主串中开始匹配的其实位置 在Java中str null和str.length 0的区别 str null表示 str 没有指向任何对象就是没有对应堆中对象 str.length() 0表示 str 指向一个字符串对象但是这个字符串长度为0 //str代表主串 sub代表子串public static int BF(String str, String sub) {if (str null || sub null) {return -1;}int lenStr str.length();int lenSub sub.length();if (lenStr 0 || lenSub 0) {return -1;}int i 0;//遍历主串int j 0;//遍历子串while (i lenStr j lenSub) {if (str.charAt(i) sub.charAt(j)) {i;j;} else {i i - j 1;j 0;}}//子串遍历完了if (j lenSub) {return i - j;}return -1;}
二、KMP算法 KMP算法是一种改进的字符串匹配算法由D.E.KnuthJ.H.Morris和V.R.Pratt提出的因此人们称它为克努特莫里斯一普拉特操作(简称KMP算法) 。KMP算法的核心是利用匹配失败后的信息尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next( )函数实现函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(mn) ---这段话来自百度百科 1. KMP算法解决的问题
对某些情况下的BF算法进行优化 BF算法每次字符串匹配失败子串的 j 都会回到子串的第一个字符但是我们看下面这个图会发现在有些情况下这样的回退是没必要的 当 i 和 j 都匹配到下标为5的字符时发现主串和字串的字符不匹配BF算法在此时就会将i 回退到主串下标1字符bj回退到子串0下标重新进行匹配既然是匹配到最后一个字符才失败那么 i 前面和 j 前面一定有一部分是相同的这里相同部分就是主串01和34下标都是ab字符串我们发现此时 j 回退到2下标c位置重新开始合适i 直接不回退 区别: KMP 和 BF 唯一不一样的地方在,我主串的 i 并不会回退并且 j 也不会移动到 0 号位置而是回退到一个特殊的位置 2.图解演示 3. 为什么主串 i 不回退? 在下面这种情况下在下标2位置匹配失败i 即使回退到1位置也是没有必要的因为 i回退到1位置的字符b 和 子串下标0位置的字符a 也不一样 4. j 的怎么进行位置的回退——引出next数组 从上面KMP算法解决的问题可知 此时匹配失败我们不回退 i 因为在这个地方匹配失败说明 i 的前面和 j 的前面是有部分是相同的不然两个下标不可能走到这里来所以 j 回退到2下标i 不回退这就是最好的情况 那么我们怎么知道 j 回退到哪个位置呢由此引入了next数组 KMP 的精髓就是 next 数组: 这个数组用来保存某个位置匹配失败后回退的位置 也就是用 next[ i ] k来表示不同的 i 来对应一个k值 这个 k 就是你将来要移动的i要移动的位置 就拿上面的例子来说j 回退到2下标 那么next数组中 next [ 5 ] 2 而 K 的值是这样求的求next数组: (1) 规则: 在子串中找到匹配成功部分的两个相等的真子串(不包含本身)一个以下标 0 开始另一个以-1 下标结尾。 (2) 不管什么数据 next[0] -1;next1] 0;在这里我们以下标来开始而说到的第几个第几个是从 1 开始也有些地方next[0] 0;next1] 1 同样以上面的子串 abcabc 为例求他的next数组 下标0和下标1是固定的那就不用说 下标2 j 处于下标2 我们就看有没有一个字符串 以下标0a字符开始 另一个字符串以下标 -1b字符结束 的两个相同的字符串 ab这三个字符中肯定没有 所以next [2] 0 下标3j 处于下标3 我们就看有没有一个字符串 以下标0a字符开始 另一个字符串以下标 -1c字符结束 的两个相同的字符串 abc这三个字符中肯定没有 所以next [3] 0 下标4j处于下标4我们同样看 有没有一个字符串 以下标0a字符开始 另一个字符串以下标 -1a字符结束 的两个相同的字符串 abca这三个字符中是有相同字符串a的 所以next [4] 1这里的1代表相同字符串的长度,没有就为0 下标5 j处于下标5 abcab 中ab 为相同的(一个a开头 另一个b结尾)字符串 所以next [5] 2 求next数组的练习: 跟上面的过程一样如果不懂可以去看 博哥视频讲解的KMP算法 30min的位置 练习 1: 举例对于”ababcabcdabcde”求其的 next 数组? 答案 -10012012001200 练习 2: 再对”abcabcabcabcdabcde”,求其的 next 数组? 答案 -10001 2345678901230 一般情况答案都是next[0] 0;next1] 1所以我们在此答案基础上全部1即可
从上面的答案我们可以得出结论数组在增的时候都是一个一个1不可能跳着加 到这里大家对如何求next数组应该问题不大了接下来的问题就是 :
5.已知next[ i ] k;怎么求next[i1]?
如果我们能够通过 next [ i ]的值,通过一系列转换得到 next [ i1]得值那么我们就能够实现这部分
首先假设: next[ i ] k 成立 (为了方便数组名命名为p
那么就有这个式子成立:p [ 0 ]...p [ k-1 ] p [ x ] ..p [ i-1 ]
因为 i -1 -k k -1 那么 x i - k 也就是p [ 0 ]...p [ k-1 ] p [ i - k ] ..p [ i-1 ]
到这一步: 我们再假设如果 p [ k ] p [ i ] ;在上面得到的式子两边加上这个式子 我们可以得到p [ 0 ]...p [ k ] p [ i-k ] ..p [ i ] ;那这个就是 next[ i1] k1; 那么: p[ i ] ! p[ k ] 呢?
看如下实例: 一次不匹配 j 回退到 2下标位置 不一定是你要找的
继续回退 此时回退到了0下标 也就是说 k一直回退 去找 p [i] p [k] ,这样就满足了p [ k ] p [ i ]) 6.KMP算法代码实现
//找到子串在主串当中的下标public static int KMP(String str,String sub,int pos) {if(str null||sub null) return -1;int lenStr str.length();int lenSub sub.length();if(lenStr 0||lenSub 0) return -1;if(pos0 || pos lenStr) return -1;int [] next new int[lenSub];getNext(sub,next);int i pos;//从pos位置开始遍历主串int j 0;//遍历子串while(i lenStr j lenSub) {//这里要考虑到一开始就不匹配j-1if (j-1||str.charAt(i) sub.charAt(j)) {i;j;} else {//下标不一样一直回退j next[j];}}if(jlenSub) {return i-j;}return -1;}//重点求子串的next数组public static void getNext(String sub,int [] next) {next[0] -1;next[1] 0;int i 2;//i表示所求next数组的下标是提前走了一步的int k 0;//比较是否相等的前一项的k//这里next[i]就是要求的和我们分析的next[i1]一样// 原来判断的是p[i]p[k]现在应该判断p[i-1]p[k]while(i sub.length()) {//此处要考虑k回退到了-1位置next值就为0if (k-1||sub.charAt(i-1) sub.charAt(k)) {next[i] k1;k;i;} else {//p[i-1]p[k]则k继续回退k next[k];}}} 7.next数组的优化 为什么要对next数组进行优化 有如下串:aaaaaaaab,他的 next 数组是-1,0,1,2,3,4,5,6,7 假设5位置匹配失败那么就得回退到4位置4位置和5位置都是a那么还得回退到3位置而3位置和4位置都是a还得继续回退就这样一直回退到0位置由此引入了nextval数组进行了优化 next 数组的优化即如何得到 nextval 数组: 1回退到的位置和当前字符一样就写回退那个位置的nextval值 2如果回退到的位置和当前字符不一样就写当前字符原来的next值 就以上面字符串为例 0下标肯定还是为-1 1下标这个位置回退到0位置因为这个位置的值和0位置回退的位置的值一样所以这个位置的值就写回退位置的值即-1 2-7下标这些位置回退到前一个位置值都是一样的所以都是-1 8下标: 回退到的位置和当前字符不一样直接写next[ 8 ]的值7即可 则修正后的数组 nextval 是:-1 -1-1-1 -1 -1 -1 -17。 练习: 模式串 tabgabbcabcaabdab’该模式串的 next 数组的值为 ( D )nextva1 数组的值为 (F) 答案在下面答案的基础上1即可选择 这里也不做过多的解释过程跟上面一样不懂的可以评论区或者私信问我或者 看博哥视频讲解的KMP算法 2h的位置 本次内容就到此啦欢迎评论区或者私信交流觉得笔者写的还可以或者自己有些许收获的麻烦铁汁们动动小手给俺来个一键三连万分感谢 !
