KMP算法--解決字符串匹配問題--模式串是否在文本串出現過
*利用之前判斷過的信息，通過next數組保存最長公共子序列的長度
*搜索詞/模式串 移動的位數=已匹配的字符數-對應的部分匹配值
在韓的例子里ABCDABD 初次匹配匹配了ABCDAB 6位，對應2，所以移動6-2=4位
e.g.
文本串 aabaabaaf
模式串 aabaaf

模式串的前綴：
    a
    aa
    aab
    aaba
    aabaa

模式串的后綴：
        f
       af
      aaf
     baaf
    abaaf

最長公共子序列的長度：
    a          0  
    aa         1 （a和a）
    aab        0
    aaba       1 （a和a）
    aabaa      2 （a和a，aa和aa）
    aabaaf     0

前綴表：010120

從索引為2的位置開始繼續匹配


package LeetcodeExercise;

import java.util.Arrays;

/**
 * @author: JESSICA
 * @description: TODO
 * @date: 2023/8/30 16:52
 * @version: 1.0
 */
public class KMP {
    public static void main(String[] args) {
        String text_string = "BBC ABCDAB ABCDABCDABDE";
        String pattern_string = "ABCDABD";

        int[] next = kmpNext(pattern_string);
        System.out.println(Arrays.toString(next));
        int index = kmpSearch(text_string, pattern_string, next);
        System.out.println(index);
    }


    //獲取一個字符串的部分匹配值表
    public static int[] kmpNext(String dest){
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i = 1, j = 0; i < dest.length(); i++){
            //找前后綴的相同的字符 當不相等時，令j向前一位 取next[j-1] 從這里更新j
            while(j > 0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j-1];
            }
            //找前后綴的相同的字符 當相等時，j++，即部分匹配值+1
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    public static int kmpSearch(String text_string, String pattern_string, int[] next){
        for(int i = 0, j = 0; i < text_string.length(); i++){
            //不匹配時，j需要重定向--kmp核心
            while (j > 0 && text_string.charAt(i) != pattern_string.charAt(j)){
                j = next[j-1];
            }
            if(text_string.charAt(i) == pattern_string.charAt(j)){
                j++;//相同，繼續向后查找
            }
            //j就是在模式串定位 長度一樣相當于每一個字符都匹配了
            if(j == pattern_string.length()){
                return i-j+1;
            }
        }
        return -1;
    }



}