一、應用場景-字符串匹配問題

字符串匹配問題:

有一個字符串 str1= ““硅硅谷尚硅谷你尚硅尚硅谷你尚硅谷你尚硅你好””，和一個子串 str2=“尚硅谷你尚硅你”
現(xiàn)在要判斷 str1 是否含有 str2, 如果存在，就返回第一次出現(xiàn)的位置, 如果沒有，則返回-1

二、暴力匹配算法

如果用暴力匹配的思路，并假設現(xiàn)在 str1 匹配到 i 位置，子串 str2 匹配到 j 位置，則有:

如果當前字符匹配成功(即str1[i]==str2[j])，則i++，j++，繼續(xù)匹配下一個字符
如果失配(即str1[i]!=str2[j])，令i=i-(j-1)，j=0。相當于每次匹配失敗時，i回溯，j被置為0。
用暴力方法解決的話就會有大量的回溯，每次只移動一位，若是不匹配，移動到下一位接著判斷，浪費了大量
的時間。(不可行!)
暴力匹配算法實現(xiàn).
代碼

package kmp;

/**
 * @program: text
 * @description: 暴力匹配算法
 * @author: min
 * @create: 2019-10-16 17:26
 **/
public class ViolenceMatch {
    public static void main(String[] args) {
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "尚硅谷你尚硅你~";
        int index = violenceMatch(str1, str2);
        System.out.println("index=" + index);
    }

    /**
     * 暴力匹配算法實現(xiàn)
     *
     * @param str1
     * @param str2
     * @return
     */
    private static int violenceMatch(String str1, String str2) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();

        int s1Len = s1.length;
        int s2Len = s2.length;

        int i = 0; // i索引指向s1
        int j = 0; // j索引指向s2

        while (i < s1Len && j < s2Len) {// 保證匹配時，不越界
            if (s1[i] == s2[j]) {//匹配 ok
                i++;
                j++;
            } else { //沒有匹配成功
                //如果失配(即 str1[i]! = str2[j])，令 i = i - (j - 1)，j = 0。
                i = i - (j - 1);
                j = 0;
            }
        }

        //判斷是否匹配成功
        if (j == s2Len) {
            return i - j;
        } else {
            return -1;
        }
    }
}

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253

三、KMP算法介紹

KMP 是一個解決模式串在文本串是否出現(xiàn)過，如果出現(xiàn)過，最早出現(xiàn)的位置的經(jīng)典算法
Knuth-Morris-Pratt 字符串查找算法，簡稱為 “KMP 算法”，常用于在一個文本串 S 內(nèi)查找一個模式串 P 的出現(xiàn)位置，這個算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年聯(lián)合發(fā)表，故取這 3 人的姓氏命名此算法.
KMP 方法算法就利用之前判斷過信息，通過一個 next 數(shù)組，保存模式串中前后最長公共子序列的長度，每次回溯時，通過 next 數(shù)組找到，前面匹配過的位置，省去了大量的計算時間

四、KMP 算法最佳應用-字符串匹配問題

字符串匹配問題:

有一個字符串str1=“BBCABCDABABCDABCDABDE”，和一個子串str2=“ABCDABD”
現(xiàn)在要判斷 str1 是否含有 str2, 如果存在，就返回第一次出現(xiàn)的位置, 如果沒有，則返回-1
要求:使用KMP算法完成判斷，不能使用簡單的暴力匹配算法.

思路分析圖解

舉例來說，有一個字符串 Str1 = “BBC ABCDAB ABCDABCDABDE”，判斷，里面是否包含另一個字符串 Str2 = “ABCDABD”?
1.首先，用 Str1 的第一個字符和 Str2 的第一個字符去比較，不符合，關(guān)鍵詞向后移動一位

2. 重復第一步，還是不符合，再后移

3. 一直重復，直到Str1有一個字符與Str2的第一個字符符合為止

4. 接著比較字符串和搜索詞的下一個字符，還是符合。

5.遇到 Str1 有一個字符與 Str2 對應的字符不符合。

6.這時候，想到的是繼續(xù)遍歷 Str1 的下一個字符，重復第 1 步。(其實是很不明智的，因為此時 BCD 已經(jīng)比較過了，沒有必要再做重復的工作，一個基本事實是，當空格與 D 不匹配時，你其實知道前面六個字符是”ABCDAB”。 KMP 算法的想法是，設法利用這個已知信息，不要把”搜索位置”移回已經(jīng)比較過的位置，繼續(xù)把它向后移，這樣就提高了效率。)

7.怎么做到把剛剛重復的步驟省略掉?可以對 Str2 計算出一張《部分匹配表》，這張表的產(chǎn)生在后面介紹

8.已知空格與 D 不匹配時，前面六個字符”ABCDAB”是匹配的。查表可知，最后一個匹配字符 B 對應的”部分匹配值”為 2，因此按照下面的公式算出向后移動的位數(shù):
移動位數(shù) = 已匹配的字符數(shù) - 對應的部分匹配值因為 6 - 2 等于 4，所以將搜索詞向后移動 4 位。

9.因為空格與C不匹配，搜索詞還要繼續(xù)往后移。這時，已匹配的字符數(shù)為 2(”AB”)，對應的”部分匹配值” 為 0。所以，移動位數(shù) = 2 - 0，結(jié)果為 2，于是將搜索詞向后移 2 位。

10.因為空格與 A 不匹配，繼續(xù)后移一位。

11.逐位比較，直到發(fā)現(xiàn) C 與 D 不匹配。于是，移動位數(shù) = 6 - 2，繼續(xù)將搜索詞向后移動 4 位。

12.逐位比較，直到搜索詞的最后一位，發(fā)現(xiàn)完全匹配，于是搜索完成。如果還要繼續(xù)搜索(即找出全部匹配)，移動位數(shù) = 7 - 0，再將搜索詞向后移動 7 位，這里就不再重復了。

13.介紹《部分匹配表》怎么產(chǎn)生的先介紹前綴，后綴是什么

“部分匹配值”就是”前綴”和”后綴”的最長的共有元素的長度。以”ABCDABD”為例， -”A”的前綴和后綴都為空集，共有元素的長度為 0; -”AB”的前綴為[A]，后綴為[B]，共有元素的長度為 0;
-”ABC”的前綴為[A, AB]，后綴為[BC, C]，共有元素的長度 0;
-”ABCD”的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長度為 0;
-”ABCDA”的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為”A”，長度為 1; -”ABCDAB”的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為”AB”，長度為 2;
-”ABCDABD”的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為 0。

14.”部分匹配”的實質(zhì)是，有時候，字符串頭部和尾部會有重復。比如，”ABCDAB”之中有兩個”AB”，那么它的”部分匹配值”就是 2(”AB”的長度)。搜索詞移動的時候，第一個”AB”向后移動 4 位(字符串長度- 部分匹配值)，就可以來到第二個”AB”的位置。

到此 KMP 算法思想分析完畢!

五、代碼實現(xiàn)

package kmp;

import JAVA.util.Arrays;

/**
 * @program: text
 * @description: kmp算法
 * @author: min
 * @create: 2019-10-17 16:08
 **/
public class KMPAlgorithm {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        //String str2 = "BBC";
        int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
        System.out.println("next=" + Arrays.toString(next));
        int index = kmpSearch(str1, str2, next);
        System.out.println("index=" + index); // 15 了

    }

    /**
     * @param str1 源字符串
     * @param str2 子串
     * @param next 部分匹配表, 是子串對應的部分匹配表
     * @return 如果是-1 就是沒有匹配到，否則返回第一個匹配的位置
     */
    public static int kmpSearch(String str1, String str2, int[] next) {
        //遍歷
        for (int i = 0, j = 0; i < str1.length(); i++) {
            //需要處理 str1.charAt(i) != str2.charAt(j), 去調(diào)整 j 的大小
            //KMP 算法核心點, 可以驗證...
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }

            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {//找到了 // j = 3 i
                return i - j + 1;
            }
        }
        return -1;
    }

    //獲取到一個字符串(子串) 的部分匹配值表
    public static int[] kmpNext(String dest) {
        //創(chuàng)建一個 next 數(shù)組保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; //如果字符串是長度為 1 部分匹配值就是 0
        for (int i = 1, j = 0; i < dest.length(); i++) {
            //當 dest.charAt(i) != dest.charAt(j) ，我們需要從 next[j-1]獲取新的 j
            //直到我們發(fā)現(xiàn) 有 dest.charAt(i) == dest.charAt(j)成立才退出
            //這時 kmp 算法的核心點
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }

            //當 dest.charAt(i) == dest.charAt(j) 滿足時，部分匹配值就是+1
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}