KMP算法详解

文章目录

• • KMP算法详解
• 前言
• 一、示例
• 二、用朴素的字符串匹配算法
• 三、KMP算法实现
• • • 1、KMP算法思路
    • 2、next数组的本质
    • 3、next数组带入思路实现
    • 4、next数组的求法
• 四、代码实现
• • • C语言实现
    • Java语言实现

前言

KMP算法是目前字符串算法里面最高校效的一种算法，相较于朴素的字符串匹配算法，其时间复杂度低得多

提示：以下是本篇文章正文内容，下面案例可供参考

一、示例

给定一个字符串s = “abcabcabd” 另一字符串t = “abcabd”，在s中查找t是否存在，若存在返回t[0]在s中对应的下标（本例应当返回3）

二、用朴素的字符串匹配算法

朴素字符串匹配算法实现：

1.  返回a的下标3
   

低效原因：
字符串s中元素被多次重复比较，通过第1步，我们就能知道s[2]是b, s[3]是c，s[4]是a，而t串串首元素是a，所以t串可以直接移动到第4步的样子，第2、3步完全多余，可以省略。

三、KMP算法实现

1、KMP算法思路

KMP算法就是为了解决上述问题而发明的，其思想核心就是t串在比对后移的过程中不是一位一位的移动，而是按照自身规律向后跳转，如上例，直接实现从第一步到第四步的跳转。而我们怎么知道自己应该往后跳几步呢，这就涉及到KMP算法的另一个重要部分，next数组。

2、next数组的本质

next数组是t串的一个属性，next[i]表示字符串前i+1位前缀跟后缀相同的位数(有些参考资料上的表示方式不同，但是内核相同)，比如上例abcabd，next[0] = 0, next[1]为前两位ab,前后缀无相同项, next[1] = 0，next[2]表示abc，也为0, 而next[3]表示abca前缀a与后缀a相等next[3] = 1, next[4]表示abcdab, 其中ab相等，next[4] = 2,next[5]表示abcabd, 无相等项，next[5] = 0.
所以t的next数组为

3、next数组带入思路实现

引入两个指针（这个指针不是指指针类型）i在s串上移动，j在t上移动。上例经过第一次循环

朴素的字符串匹配算法此时的j就需要回溯到t[0]的位置i要回溯到s[1]的位置。如下图

而kmp算法的i不需要回溯，j只需要回溯到 next[j-1] 就行
为什么是next[j-1]而不是next[j]，因为当循环退出的时候，j还++了一下，而next记录的是它++前的数值，所以要减一下
即

//（上图为朴素字符串匹配算法，此图接上上图）此时j等于5则next[4] = 2
while(j>0 && t[j] != s[i]){ 
	j = next[j];
}
	//意思就是，如果回溯一次还是不匹配的话，就回溯两次，我这次回溯一次后
	//t[j]等于t[2]等于c刚好与此时的s[i]相等，就不用继续回溯了，退出循环

然后i、j往后移动，直到j到达最后一位且匹配成功或者是i超过了范围，前者匹配成功，后者匹配失败。

4、next数组的求法

那么上述的思路应该很清晰了，还剩最后一个问题，next数组是怎么得到的呢，还用常规遍历的话，复杂度应该是非常高的，一直在重复比对。next数组的求法我个人感觉就是KMP算法的精髓。
我们开始默认next[0] = 0，有了初始值我们就可以想办法采用动态规划的思想来解决这个问题。
还是先申明两个指针i和j，仍拿t串模拟由于已知next[0]那么i就从1开始

s[j] != s[i]
//移动i，j不动

s[j] != s[i]
//移动i，j不动

s[j] == s[i]
next[i] = next[i-1] + 1
//移动i，j也移动

s[j] == s[i]
next[i] = next[i-1] + 1
//移动i，j也移动

s[j] != s[i]
//移动i，j回溯
j = next[j]
//若一直s[j] != s[i]则一直回溯，直到s[i] == s[j]或者是j回溯到0

然后t[i] != t[j] next[i] = 0;
即可求出next数组。

四、代码实现

C语言实现

#include <stdio.h>
#include <cstring>

void getNext(char t[], int next[]){ 
    next[0] = 0;
    for(int i = 1, j = 0; i < strlen(t); i++){ 
        while (j > 0 && t[i] != t[j]){ //abcabd
            //000120
            j = next[j-1];
        }
        if(t[i] == t[j]){ 
            j++;
        }
        next[i] = j;
    }
}


int KMP(char *s, char *t) { 
    int next[6];
    getNext(t, next);
    for(int i = 0, j = 0; i < strlen(s); i++){ 
        while(s[i] != t[j] && j>0) { 
            j = next[j];
        }
        if(s[i] == t[j]){ 
            j++;
        }
        if(strlen(t) == j) return i-j+1;
        if(strlen(s) == i) return false;
    }
}


int main(){ 
    char t[7] = "abcabd";
    char s[15] = "abcababcabd";
    int next[6];
    getNext(t, next);
    int index = KMP(s, t);
    if(index){ 
        printf("已匹配，下标为：%d\n", index);
    }
    else
        printf("无匹配字符串\n");
    return 0;
}

Java语言实现

package KMP;

public class KMP { 

    public int[] getNext(String t){ 
        int[] next = new int[t.length()];
        next[0] = 0;
        int i = 1, j = 0;
        while (i < t.length()) { 
            while (j > 0 && t.charAt(i) != t.charAt(j)){ 
                j = next[j];
            }
            if (t.charAt(i) == t.charAt(j)){ 
                j++;
            }
            next[i] = j;
            i++;
        }
        return next;
    }

    public int kmp(String t, String s){ 
        int[] next = getNext(t);
        for (int i = 0, j = 0; i < s.length(); i++){ 
            while (t.charAt(j) != s.charAt(i) && j > 0){ 
                j = next[j];
            }
            if (t.charAt(j) == s.charAt(i)){ 
                j++;
            }
            if (j == t.length()){ 
                System.out.println("找到了且下标为" + (i-j+1));
                return i-j+1;
            }
        }
        return 0;
    }

    public static void main(String[] args) { 
        String s = "abcdabcdx";
        String t = "abcdx";
        new KMP().kmp(t, s);
    }

}