KMP算法--解决字符串匹配问题--模式串是否在文本串出现过-JZTXT

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;
    }



}