kmp案例

package com.atguigu.kmp;
import java.util.Arrays;
/**
 * KMP算法 --- 字符串匹配问题
 *
 * @author Dxkstart
 * @create 2022-04-13-9:36
 */
public class KMP {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] ints = KMP.kmpNext(str2);
        System.out.println(Arrays.toString(ints));
        int index = KMP.kmpSearch(str1, str2, ints);
        System.out.println("位置：" + index); // 15
    }
    // 获取到一个字符串的部分匹配值 --> 是给定的子串的部分匹配表
    public static int[] kmpNext(String str2) {
        // 创建一个next数组保存部分匹配值
        int[] next = new int[str2.length()];
        // 不管字符串的长度多长，第一位始终是0
        next[0] = 0;
        // j指向str2 ， i指向next[]
        for (int i = 1, j = 0; i < str2.length(); i++) {
            // 这个while是老师说的kmp核心，但是我把next[i] = j;放到if语句中，照样可以实现
            // 原先next[i] = j;是在if外面的，我这样改进暂时没有出现问题
//            while (j > 0 && str2.charAt(i) != str2.charAt(j)) {
//                j = next[j-1];
//            }
            if (str2.charAt(i) == str2.charAt(j)) {
                j++;
                next[i] = j;
            }
        }
        return next;
    }
    // KMP搜索算法
    /**
     * @param str1 源字符串
     * @param str2 子串
     * @param next 子串的部分匹配表
     * @return 返回第一个匹配的位置
     */
    public static int kmpSearch(String str1, String str2, int[] next) {
        // 遍历源字符串 i指向str1  ， j指向str2
        for (int i = 0, j = 0; i < str1.length(); i++) {
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            } else {
                // 不相等时,i指针不受影响，重新定位j指针
                if (j != 0) {
                    j = next[j - 1];
                    // 修改
                    i--;
                }
            }
            // 找到时
            if (j == str2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }
}