Java KMP算法：高效找到所有子串 |21xrx.com

Java KMP算法：高效找到所有子串

2023-10-27 21:14:01 深夜i 19 0

Java KMP算法高效找到子串

Java KMP算法是一种高效的字符串匹配算法，能够找到目标字符串中的所有子串。它的核心思想是通过利用已匹配的部分信息来避免不必要的比较，从而提高匹配效率。

首先，我们需要了解KMP算法中的两个重要概念：前缀和后缀。对于一个字符串，它的前缀是指从开头到某一位置的子串，后缀则是指从某一位置到尾部的子串。

KMP算法的实现需要用到一个辅助数组next[]，它记录了目标串中每个位置前面最长的既是前缀又是后缀的子串的长度。通过这个数组，我们可以跳过不必要的比较，直接将模式串向后移动到合适的位置，从而减少了比较次数。

具体的实现步骤如下：

1. 初始化两个指针i和j，分别指向目标串和模式串的起始位置。

2. 如果目标串和模式串当前位置的字符相等，i和j分别向后移动一位。

3. 如果j已经到达模式串的末尾，说明匹配成功，记录当前位置，并将j移动到next[j]的位置，继续向下匹配。

4. 如果当前位置的字符不相等，根据next[j]的值将j移动到合适的位置。

5. 重复步骤2-4，直到目标串或模式串遍历完毕。

下面是一个使用Java实现KMP算法的例子：

public class KMP {
  public static List<Integer> findAll(String target, String pattern) {
    int[] next = getNext(pattern);
    int i = 0, j = 0;
    List<Integer> result = new ArrayList<>();
    while (i < target.length()) {
      if (target.charAt(i) == pattern.charAt(j)) {
        i++;
        j++;
        if (j == pattern.length()) {
          result.add(i - j);
          j = next[j];
        }
      } else {
        j = next[j];
        if (j == -1) {
          i++;
          j++;
        }
      }
    }
    return result;
  }
  private static int[] getNext(String pattern) {
    int[] next = new int[pattern.length() + 1];
    next[0] = -1;
    int i = 0, j = -1;
    while (i < pattern.length()) {
      if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
        i++;
        j++;
        next[i] = j;
      } else {
        j = next[j];
      }
    }
    return next;
  }
  public static void main(String[] args) {
    String target = "abababab";
    String pattern = "ab";
    List<Integer> result = findAll(target, pattern);
    System.out.println(result);
  }
}

在上述代码中，我们定义了一个`findAll`函数，它通过调用`getNext`函数来获取模式串的辅助数组，并且使用两个指针`i`和`j`来遍历目标串和模式串。最后，我们通过调用`findAll`函数来找到目标串中所有匹配模式串的子串的位置。

总结来说，Java KMP算法是一种高效的字符串匹配算法，通过利用辅助数组来避免不必要的比较，能够快速找到目标串中的所有子串。它的实现思路简单明了，而且在实际应用中具有较高的效率，是一种非常有用的算法。

上一篇: idea打包java可执行jar包

下一篇: Java中的除法运算如何实现

评论区

相似文章