KMP算法

package com.yt.string;
import java.util.Arrays;
import java.util.Objects;
/**
 * @类描述: 找出字符串中第一个匹配的下标，LeetCode 28
 * @作者: **
 * @日期: ***
 */
public class StrStr {
    public static int strStr(String haystack, String needle) {
        //KMP算法
        System.out.println("haystack: " + haystack);
        System.out.println("needle:   " + needle);
        //如果模式串为空返回0
        Objects.requireNonNull(haystack);
        Objects.requireNonNull(needle);
        if ("".equals(needle)) {
            return 0;
        }
        int[] prefixTable = calculatePrefixTable(needle);
        int[] next = convertToNext(prefixTable);
        int res = doStrStr(haystack, needle, next);
        System.out.println("        结果：" + res);
        return res;
    }
    /**
     * @param needle 模式串
     * @return 前缀表
     */
    private static int[] calculatePrefixTable(String needle) {
        int[] prefixTable = new int[needle.length()];
        prefixTable[0] = 0;
        for (int i = 1; i < prefixTable.length; i++) {
            int nIndex = i - 1;// 第i个字符前的字符串的n级等缀在前缀表的索引
            int nLength = prefixTable[nIndex];// 第i个字符前的字符串的n级缀长
            while (true) {
                if (needle.charAt(i) == needle.charAt(nLength)) {
                    prefixTable[i] = nLength + 1;
                    break;
                } else {
                    if (nLength == 0) {
                        prefixTable[i] = 0;
                        break;
                    }
                    nLength = prefixTable[nLength - 1];
                }
            }
        }
        System.out.println("    前缀表：   " + Arrays.toString(prefixTable));
        return prefixTable;
    }
    /**
     * 将前缀表转换为next数组，使用前缀表右移一位并初始值赋-1实现
     *
     * @param prefixTable 前缀表
     * @return next数组
     */
    private static int[] convertToNext(int[] prefixTable) {
        int[] next = new int[prefixTable.length];
        next[0] = -1;
        System.arraycopy(prefixTable, 0, next, 1, next.length - 1);
        System.out.println("    next数组：" + Arrays.toString(next));
        return next;
    }
    /**
     * 找出字符串中第1个匹配项的下标
     *
     * @param haystack 文本串
     * @param needle   模式串
     * @param next     next数组
     * @return 匹配项的下标，如果没有匹配项返回-1
     */
    private static int doStrStr(String haystack, String needle, int[] next) {
        int i = 0, j = 0;// i为haystack下标，j为needle下标
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                if (j == needle.length()) {
                    return i - needle.length();
                }
            } else {
                j = next[j];
                if (j == -1) {
                    i++;
                    j++;
                }
            }
        }
        return -1;
    }
}