什么是KMP演算法？

KMP 演算法是一種改進的字串匹配演算法/ 找子串的演算法的改進，由D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人們稱它為克努特 - 莫里斯 - 普拉特操作（簡稱 KMP演算法），KMP演算法的核心是利用匹配失敗后的資訊，盡量減少 模式串 和 主串 的匹配次數以達到快速匹配的目的、具體實作就是通過一個next()函式實作（其實更準確的來說是一個next陣列），函式本身包含了 模式串/子串 的 區域匹配資訊，KMP演算法的時間復雜度O(M+N)[1]， ——來自百度百科

?

KMP 與 BF（暴力解法）的區別

KMP 和 BF 唯一不一樣的地方在：
當給你一個主串 和 模式串/子串，要你來查找主串是否包含子串，包含就回傳 主串中子串的起始的位置，
現在用來遍歷主串的變數 i 和 遍歷子串的 變數 j，指向字符不匹配時，就意味著 目前 主串中 匹配的字串 與 子串不相等，也就是說：目前從主串的某一種位置開始，一直到匹配字符不相等的位置之間，與子串不匹配，
KMP ：我主串的 i 并不會回退，并且 j 也不會回到下標0的位置，（這個就是接下來要搞懂的東西）
BF： 我主串的 i 回退 原來 匹配開始的位置，并加一，而 子串的 j 直接回到 下標為0 的 位置，然后繼續匹配，

?

附圖

?

KMP 的 遍歷 子串變數 j 的 回退機制

到這里就不用翻了哦，因為截圖，達到了最大限度，所以我不得不將其分割成兩部分，希望不會影響到大家，

?

練習（加深 求 next 陣列 的印象）

練習一

?

練習二

?

接下來，又是推理時間: 如何用程式去 求 k值 / 求 next 陣列的元素

?

Java 實作 KMP 演算法

public class Manuscript {
    /*
    * @param str 主串
    * @param sub 子串
    * @param pos 從主串的pos位置開始匹配
    * @return  找到 子串 在主串當中的 下標
    * */
    public static int KMP(String str,String sub,int pos){
        if (str == null || sub == null){
//不管是主串，還是子串為null，你都查找不了 子串 在 主串中的位置
            return  -1;// 此時回傳回傳-1 表示找不到，或者說無法查找
        }

        int lenStr = str.length();//獲取主串的長度
        int lenSub = sub.length();//獲取子串的長度

        if(lenStr == 0 || lenStr==0){
 // 這種情況也不用去想，空字串里面一個元素都沒有，肯定也比不了！
            return  -1;
        }
        if (pos < 0 || pos > str.length()){
            // 你規定查找位置不合法，如果不寫，很可能會導致越界例外，導致程式終止
            return -1;
        }

        int i = pos;// 從指定的 pos 位置，開始遍歷 主串
        int j = 0;// 遍歷 子串

        int[] next = new int[lenSub];// 創建一個 next陣列，長度 與 子串一致
        getNext(sub,next);// 得到next 陣列

        while(i < lenStr && j < lenSub){
            if(j==-1 || str.charAt(i)==sub.charAt(j)){// 這就是主串 和 子串匹配成功的情況
                //  j == -1. 是為了處理i 和 j 指向字符不匹配的情況
                //  j 回退的時候，在next陣列中，一直沒有 p[j] == p[k]的情況出現
                // j 回退到 -1 的情況，也就是沒有相同的真子串情況 p[0]~ p[k-1] != p[j-k] ~ p[j-1]
                // 另外 這個條件需要放在前面，放在后 charAt一讀取，就會發生越界例外
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        if (j >=lenSub){
            return i-j;
        }
        // 主串 不包含 子串的情況，也就是 i 與 j 不匹配，j 一直在子串的下標0位置待命
        // 即 j < lenSub
        return -1;

    }
    public static void getNext(String sub,int[] next){
        next[0] = -1;
        next[1] = 0;
        int j = 2;// 提前走了一步
        int k = 0;
        while(j< sub.length()){// 遍歷 子串
            // p[j] == p[k]
            if(k== -1 || sub.charAt(j-1) == sub.charAt(k)){
                next[j] = k + 1;
                j++;
                k++;
            }else {// p[j] != p[k], j需要回退
                k = next[k];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(KMP("abababcabcdef","abcd",0));//7
        System.out.println(KMP("abababcabcabcdef","abcdf",0));// -1
        System.out.println(KMP("abababcabcabcdef","ab",0));//0
    }
}

?

附圖 （講解重要部分）

附圖 1（主串 查找 子串的程序）

附圖 2 （next陣列，實作注意情況）

?

C 實作 KMP 演算法

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
void GetNext(char*sub, int* next, int lenSub)
{
	next[0] = -1;
	next[1] = 0;
	int j = 2;
	int k = 0;
	while (j < lenSub)
	{
		if (-1 == k || sub[j - 1] == sub[k])
		{
			next[j] = k + 1;
			k++;
			j++;
		}
		else
		{
			k = next[k];
		}
	}

}

int KMP(char* str, char* sub, int pos)
{
	assert(str&&sub);//判斷 主串 和 子串是否為 NULL 指標
	int lenStr = strlen(str);
	int lenSub = strlen(sub);
	if (lenStr==0 || lenSub==0)
	{
		return -1;
	}
	if (pos < 0 || pos >= lenStr)
	{
		return -1;
	}

	int* next = (int*)malloc(sizeof(int)*lenSub);
	assert(next);// 判斷空間是否開辟失敗
	GetNext(sub, next,lenSub);

	int i = pos;
	int j = 0;

	while (i < lenStr && j < lenSub)
	{
		if (-1 == j || str[i] == sub[j])
		{
			j++;
			i++;
		}
		else
		{
			j = next[j];
		}
	}
	free(next);
	if (j >= lenSub)
	{
		return i - j;
	}
	return -1;
}





int main()
{
	printf("%d\n", KMP("abababcabcdef", "abcd", 0));// 7
	printf("%d\n", KMP("abababcabcdef", "abcdf", 0));// -1
	printf("%d\n", KMP("abababcabcdef", "ab", 0));// 0
	return 0;
}

?

KMP演算法優化 》》 next陣列優化 》》 又稱 nextval 陣列

?

練習

如果 題目 規定了 next[0] 和 next[1] 的值， 也很簡單，就按照這個模式就能寫出來，如果運氣好，題目規定 next[0] = 0; next[1] = 1，你就在我們這個結果的基礎上加一就行了，

?

文章至此就結束了，希望大家通過這封 KMP 信，能識訓頗豐!