JAVA实现KMP算法理论和示例代码

KMP算法，全称Knuth-Morris-Pratt算法，是一种高效的字符串匹配算法，相比于朴素的线性查找方法，KMP算法显著提高了匹配效率。它通过构建一个预处理的next数组，存储了模式串中每个位置发生不匹配时，可以跳过的字符数，避免了不必要的回溯，从而减少了比较次数。 在KMP算法中，`next`数组是核心。对于模式串`p`，`next[i]`表示当`p`的前`i`个字符与目标串不匹配时，可以将模式串的比较位置直接移动到`next[i]`所指的位置，而不需要重新从头开始比较。`next[i]`的值是模式串的一个最长前后缀长度，使得该前后缀相同。 例如，对于模式串`"cacca"`，它的`next`数组构建如下： - `next[2] = 0`，因为前缀`"ca"`没有相同的字符作为后缀。 - `next[3] = 1`，因为前缀`"cac"`的后缀`"ac"`与前缀相同。 - `next[4] = 1`，同理，前缀`"cacc"`的后缀`"cc"`与前缀的前两个字符相同。 - `next[5] = 2`，前缀`"cacca"`的后缀`"cca"`与前缀的前三个字符相同。 构建`next`数组的过程通常采用迭代，从第二个字符开始，利用已计算好的`next[i-1]`值，逐个比较字符直到找到最长相同前后缀，或者达到`next[k] = 0`。 在Java中实现KMP算法，首先需要初始化`next`数组，然后进行字符串匹配。以下是一个简单的Java实现： ```java public class KMP { static String str = "1kk23789456789hahha"; static String ch = "789"; static int next[] = new int[20]; public static void main(String[] args) { setNext(); ArrayList<Integer> arr = getKmp(); if (arr.size() != 0) { for (int i = 0; i < arr.size(); i++) { System.out.println("匹配发生在:" + arr.get(i)); } } else { System.out.println("匹配不成功"); } } private static void setNext() { int lenCh = ch.length(); next[0] = 0; next[1] = 1; int k = 0; for (int i = 2; i <= lenCh; i++) { k = next[k]; while (k != 0 && ch.charAt(i - 1) != ch.charAt(k)) { k = next[k]; } if (ch.charAt(i - 1) == ch.charAt(k)) { next[i] = k + 1; } else { next[i] = k; } } } private static ArrayList<Integer> getKmp() { int lenStr = str.length(); int lenCh = ch.length(); ArrayList<Integer> res = new ArrayList<>(); int j = 0; for (int i = 0; i < lenStr; i++) { while (j != 0 && str.charAt(i) != ch.charAt(j)) { j = next[j]; } if (str.charAt(i) == ch.charAt(j)) { j++; } if (j == lenCh) { res.add(i - lenCh + 1); j = next[j - 1]; } } return res; } } ``` 这段代码中，`setNext()`函数用于计算`next`数组，`getKmp()`函数则进行实际的字符串匹配。在匹配过程中，如果当前字符匹配失败，会根据`next`数组的值调整模式串的位置，继续匹配，直到找到所有匹配的位置或遍历完主串。 KMP算法通过预处理`next`数组，避免了不必要的回溯，提高了字符串匹配的效率。在Java中，通过构建并利用`next`数组，我们可以高效地实现KMP算法，解决字符串匹配问题。