算法笔记(一）——KMP算法

暴力匹配(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;
}
} i
f(j >= subLen) {
return i-j;
} r
eturn -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;//前一项的k
    int 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;//前一项的K
while(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算法的讲解，有不足的地方或者对代码有更好的见解，欢迎评论区留言共同商讨，共同进步！！