kmp算法 java

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。它的核心思想是利用已经匹配过的部分信息，尽量减少不必要的比较次数，从而提高匹配效率。

KMP算法的实现主要包括两个步骤：构建next数组和进行匹配。

1. 构建next数组：
- 首先，我们需要定义一个next数组，用于存储模式串中每个位置的最长公共前后缀长度。
- 然后，从模式串的第二个字符开始，依次计算每个位置的最长公共前后缀长度。
- 最后，将计算得到的最长公共前后缀长度填入next数组中。

2. 进行匹配：
- 在匹配过程中，我们需要维护两个指针：主串指针i和模式串指针j。
- 当主串和模式串的当前字符匹配时，i和j同时向后移动一位。
- 当主串和模式串的当前字符不匹配时，根据next数组的值调整模式串指针j的位置。
- 如果j等于模式串的长度，表示匹配成功，返回主串中匹配的起始位置。

下面是KMP算法的Java实现示例：

public class KMP {
    public static int kmp(String text, String pattern) {
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < text.length() && j < pattern.length()) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == pattern.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    private static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }
}