暴力匹配(BF)算法
基本概念
BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
分析BF算法
光看定义晦涩难懂,接下来我将举例子与大家一起学习:
假定我们给出字符串"ababcabcdabcde"做为主串,然后给出子串"abcd",现在我们需要查找子串是否在主串中出现，出现返回主串中第一个匹配的下标，失败返回-1.
对于这个问题我们很容易想到:从左到右依次匹配,如果字符相等,都向后移一位,如不相等, 子串从0下标重新开始,主串向右移动一位(假设原来从0下标开始,下次从1下标开始）
我们可以这样初始化:
根据我们的想法，之后我们就需要比较i指针和j指针指向的数字是否一致，如果一致都向后移动，如果不一致，如下图:
b和d不相等,那就把i指针回退到刚刚指针的下一个位置(刚刚指针是从0下标开始的）,j指针退回到0下标重新开始。
代码实现
根据以上的分析,下面我们开始写代码:
C代码:
#include<stdio.h>#include<string.h>#include<assert.h>int BF(char* str1, char* str2){assert(str1 != NULL && str2 != NULL);int len1 = strlen(str1);//主串的长度int len2 = strlen(str2);//子串的长度int i = 0;//主串的起始位置int j = 0;//子串的起始位置while (i < len1 && j < len2){if (str1[i] == str2[j]){i++;//相等i和j都向后移动一位j++;}else {//不相等i = i - j + 1;//i回退j = 0;//j回到0位置}}if (j >= len2) {//子串遍历玩了说明已经找到与其匹配的子串return i - j;}else {return -1;}}int main(){printf("%d\n", BF("ababcabcdabcde", "abcd"));//测试,为了验证代码是否正确尽量多举几个例子printf("%d\n", BF("ababcabcdabcde", "abcde"));return 0;}
java代码:
public class Test {public static int BF(String str,String sub) {if(str == null || sub == null) return -1;int strLen = str.length();int subLen = sub.length();int i = 0;int j = 0;while (i < strLen && j < subLen) {if(str.charAt(i) == sub.charAt(j)) {i++;j++;}else {i = i-j+1;j = 0;}} if(j >= subLen) {return i-j;} return -1;}public static void main(String[] args) {System.out.println(BF("ababcabcdabcde","abcd"));System.out.println(BF("ababcabcdabcde","abcde"));}}
牛刀小试
通过上面的学习，对BF算法有了初步的认识,为了更深刻的了解和运用，下面和大家一起完成以下试题:
试题在这里>>实现strStr()
感兴趣的伙伴可以去做试试,下一章我们进行共同探讨;
BF算法的时间复杂度
最好的情况就是从第一次开始就匹配成功时间复杂度为O(1);
最坏的情况就是每次都匹配到最后一个才发现与主串不相同,比如"aaaaab",子串”aab"
看上图，除了最后一次，其余的都是每次匹配到最后，才发现，啊，我们不一样。
这种情况下，上图中，模式串在前 3 次，每次都要匹配 3 次，并且不匹配，直到第 4 次，全部匹配，不需要继续移动，所以匹配的次数为（6 - 3 + 1）* 3 = 12 次。
由此可知，对于主串长度为 n，模式串长度为 m ，最坏情况下的时间复杂度为 O((n - m + 1) * m) = O(n * m)。
相信善于思考的小伙伴会发现，如果是为了寻找的话,根本不需要将i移动到1的位置,因为前面几个字符都是匹配的,再将i移动到1的位置,j移动到0位置,位置错开了,显然也不会匹配,那么我们能不能丢掉以上没必要的步骤,减少指针回溯进行算法简化囊,有一个想法,i位置不动,只需要移动j位置，由此引出我们今天的主人公kmp算法.
KMP算法
基本概念
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。
区别：KMP 和 BF 唯一不一样的地方在，我主串的 i 并不会回退，并且 j 也不会移动到 0 号位置
分析KMP算法
假定我们给出字符串"ababcabcdabcde"做为主串,然后给出子串"abcd",现在我们需要查找子串是否在主串中出现，出现返回主串中第一个匹配的下标，失败返回-1.
1.首先举例说明，为什么主串不回退
2.j的回退的位置
那么j是怎么回退到下标2的位置的囊？下面我们引出next数组
引出next数组
KMP 的精髓就是 next 数组：也就是用** next[j] = k**;来表示,**不同的 j 来对应一个 K 值,**这个 K 就是你将来要移动的 j要移动的位置。而 K 的值是这样求的:
- ** 规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1 下标字符结尾。**
- 不管什么数据 next[0] = -1;next[1] = 0;在这里，我们以下标来开始，而说到的第几个第几个是从 1 开始；
**求next数组的练习: **
练习一:举例对于”ababcabcdabcde”， 求其的 next 数组？
-1 0 0 1 2 0 1 2 0 0 1 2 0 0
练习 2： 再对”abcabcabcabcdabcde”,求其的 next 数组？ "
-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0
核心的东西来了:
到这里大家对如何求next数组应该问题不大了，接下来的问题就是，已知next[i] = k;怎么求next[i+1] = ?
如果我们能够通过 next[i]的值,通过一系列转换得到 next[i+1]得值，那么我们就能够实现这部分。
那该怎么做呢？
首先假设： next[i] = k 成立，那么，就有这个式子成立：P0...Pk-1 = Px...Pi-1,得到： P0...Pk-1 = Pi-k..Pi-1;如下图分析:
然后我们假设如果 Pk = Pi;我们可以得到 P0...Pk = Pi-k..Pi;那这个就是 next[i+1] = k+1;
那么： Pk != Pi 呢？
代码实现
C代码:
#include<stdio.h>#include<string.h>#include<assert.h>void GetNext(int* next, char* sub, int len2){next[0] = -1;//规定第一个为-1,第二个为0,则直接这样定义就好了;next[1] = 0;int k =0;//前一项的kint j = 2;//下一项while (j < len2){if (k==-1||sub[j-1] == sub[k]){next[j] = k + 1;j++;k++;}else{k = next[k];}}}int KMP(char* str, char* sub, int pos){assert(str != NULL && sub != NULL);int len1 = strlen(str);int len2 = strlen(sub);assert(pos >= 0 && pos < len1);int i = pos;//i从指定下标开始遍历int j = 0;int* next = (int*)malloc(sizeof(int) * len2);//动态开辟next和子串一样长assert(next != NULL);GetNext(next, sub, len2);while (i < len1 && j < len2){if (j == -1||str[i] == sub[j])//j==-1是防止next[k]回退到-1的情况{i++;j++;}else {j = next[j];//如果不相等,则用next数组找到j的下个位置}}if (j >= len2){return i - j;}else {return -1;}}int main(){char* str = "ababcabcdabcde";char* sub = "abcd";printf("%d\n", KMP(str, sub, 0));return 0;}
java代码:
public static void getNext(int[] next, String sub){next[0] = -1;next[1] = 0;int i = 2;//下一项int k = 0;//前一项的Kwhile(i < sub.length()){//next数组还没有遍历完if((k == -1) || sub.charAt(k) == sub.charAt(i-1)) {next[i] = k+1;i++;k++;}else{k = next[k];}}}public static int KMP(String s,String sub,int pos) {int i = pos;int j = 0;int lens = s.length();int lensub = sub.length();int[] next= new int[sub.length()];getNext(next,sub);while(i < lens && j < lensub){if((j == -1) || (s.charAt(i) == sub.charAt(j))){i++;j++;}else{j = next[j];}}if(j >= lensub) {return i-j;}else {return -1;}}public static void main(String[] args) {System.out.println(KMP("ababcabcdabcde","abcd",0));System.out.println(KMP("ababcabcdabcde","abcde",0));System.out.println(KMP("ababcabcdabcde","abcdef",0));}
关键代码讲解
else{
j=next[j]
}
if (j == -1||str[i] == sub[j])
{
i++;
j++;
}
问题:为啥还有个j==-1?
如下图所示:当第一个字符就不匹配,i,j此时都是0**,j=next[j] >> j=next[0] >> j=-1; **此时j是-1,如果不添加j==-1这种情况,那么这个程序将结束返回没有匹配,但你仔细观察下图,P[5]~P[8]与子串相匹配，故答案显然错误.所以我们应该加上j==-1这种情况，让其从头再遍历;
next[0] = -1;
next[1] = 0;
int k =0;//前一项的k
int j = 2;//下一项
根据我们的规定next数组第一个和第二个数为-1和0,故没啥问题。k=0是前一项k的值,j=2是下一项.
if (k==-1||sub[j-1] == sub[k])
{
next[j] = k + 1;
j++;
k++;
}
根据上面的内容我们可知,p[j]==p[k],next[i]=k;则能推出next[i+1]=k+1;如下图所示,不过这里i是j-1,大家要注意这一点, p[j]==p[k]>>sub[j-1]==sub[k];next[i+1]=k+1>>next[j]=k+1;
else
{
k = next[k];
}
这个知识点上面讲过，当p[j]!=p[k]时候,k回退，一直找到p[j]==p[k]然后用这个next[i+1]=k+1;
牛刀小试
题目在这里>>重复的子字符串
感兴趣的伙伴可以去做试试,下一章我们进行共同探讨;
KMP算法的时间复杂度
假设在M字符串中找N字符串的起始位置，长度分别为m和n，使用KMP算法，一般认为时间复杂度是**O（m+n）,**也就是计算next数组的时间复杂度是O(n)，而匹配的时候是O（m）.
以上是KMP算法的讲解，有不足的地方或者对代码有更好的见解，欢迎评论区留言共同商讨，共同进步！！
版权归原作者 skeet follower 所有， 如有侵权，请联系我们删除。