KMP算法是一種字符串匹配算法，對于指定字符串str1和子串str2，返回字串在str1出現(xiàn)的位置索引，str1中不存在子串str2返回-1

前綴表

KMP 在匹配字符串根據(jù)前綴表減少不必要的回溯

KMP首先需要根據(jù)str2構(gòu)造最長公共前后綴表
以 AABAABAAA為例
前綴

• A 最長公共前后綴為0
• AA 最長公共前后綴為1
• AAB 最長公共前后綴為0
• AABA 最長公共前后綴為1
• AABAA 最長公共前后綴為2
• AABAAB 最長公共前后綴為3
• AABAABA 最長公共前后綴為4
• AABAABAA 最長公共前后綴為5
• AABAABAAA 最長公共前后綴為2

給出計算前綴表的代碼：

    public static int[] computePrefixFunction(String str) {
        int[] next = new int[str.length()];
        next[0] = 0;
        for (int i = 1, j = 0; i < str.length(); i++) {
            //對不上
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                //hard to understand
                j = next[j - 1];

            }


            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;

    }

在這個代碼while里的 j = next[j - 1]非常不好理解, j代表的是下一個需要比較的最長公共前后綴字符串的位置，我以構(gòu)造AABAABAAA這個串的前綴表的最后兩步做一些說明，在倒數(shù)第二步時算出了AABAABAA最長公共前后綴為5 ，此時的j=5，接下來i+1=8，指向了最后字符串中的最后一個字符A，此時j對應(yīng)的字符為B和i對應(yīng)的字符不相等，需要重新定位字符j。代碼中的定位j的代碼為j = next[j - 1]，這個實際上是倒數(shù)第二步匹配到的AABAA這個串的公共前后綴，其值等于2，關(guān)鍵是為什么要這么定位呢，這也是回溯不過是基于已知串的特性，也就是開頭的兩個綠色AA和結(jié)尾出的兩個綠色AA相等，不需要比較，只需要比較接下來的黃色是否相等 給出一張圖，幫助理解：

圖中的串有如下特性

• ，這個結(jié)論在倒數(shù)第二步由AABAABAA 最長公共前后綴為5 可以得出
• ，的子串,所以需要將j定位到黃色的B出，然后比較i，j對應(yīng)的字符是否相等，不等的話繼續(xù)按照此方法回溯。

kmpSearch

具體的搜索就是利用了前面提到的前綴表，思想基本一致，通過前綴表對齊str1 ,str2,直接上代碼

import java.util.Arrays;

/****
 i
 0   1   2   3   4   5   6   7   8
 A   A   B   A   A   B   A   A   A
 0   1   0   1   2   3   4   5

 i
 0   1   2   3   4   5   6   7   8
 A   A   B   A   A   B   A   A   A
 j

 0   1   oo
 A   A   B   A   A   B
 A   A   B   A   A   A
 */

public class KMP {


    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
//        String str2 = "AABAABAAA";
        String str2 = "ABCDABD";
        int[] prefixTable = computePrefixFunction(str2);
        System.out.println(Arrays.toString(prefixTable));
        System.out.println(kmpSearch(str1, str2, prefixTable));

    }

    /**
     * @param str 字符串
     * @return 字符串的最大公共前后綴
     */
    public static int[] computePrefixFunction(String str) {
        int[] next = new int[str.length()];
        next[0] = 0;
        for (int i = 1, j = 0; i < str.length(); i++) {
            //對不上
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                //hard to understand
                j = next[j - 1];

            }


            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;

    }

    public static int kmpSearch(String str1, String str2, int[] prefixTable) {
        for (int i = 0, j = 0; i < str1.length(); i++) {
            //匹配不上時，查詢前綴表
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                //根據(jù)前綴表對齊str2的 j下標(biāo)，減少比較
                j = prefixTable[j - 1];
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {
                return i - j + 1;
            }

        }
        return -1;
    }


}

時間復(fù)雜度

如果str1的長度為n，str2的長度為m

• computePrefixFunction時間復(fù)雜度為O(m)
• kmpSearch時間復(fù)雜度為O(n)