使用Java的KMP算法找到所有子串 |21xrx.com

使用Java的KMP算法找到所有子串

2023-07-30 01:43:04 深夜i -- --

Java KMP算法子串查找匹配

KMP算法（Knuth-Morris-Pratt算法）是一种用于字符串匹配的高效算法，其核心思想是利用已经匹配过的信息，避免不必要的比较。本文将介绍如何使用Java实现KMP算法，并找到指定字符串中所有的子串。

KMP算法基于一个主串和一个模式串的匹配过程。主串是待匹配的原始字符串，而模式串是需要在主串中查找的子串。KMP算法通过预处理模式串，生成一个部分匹配表（也称为next数组），用于指导匹配过程的跳转操作。

首先，我们需要创建一个函数来生成部分匹配表。该函数需要接受一个模式串作为输入，并返回一个整型数组，表示每个位置上的最长可匹配前缀的长度。

下面是生成部分匹配表的Java代码示例：


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

接下来，我们需要实现一个函数，来利用生成的部分匹配表进行字符串匹配。该函数需要接受主串和模式串作为输入，并返回一个整型数组，表示模式串在主串中出现的所有位置。

下面是利用KMP算法进行字符串匹配的Java代码示例：


public List<Integer> findSubstring(String text, String pattern) {
  List<Integer> positions = new ArrayList<>();
  int[] next = generateNextArray(pattern);
  int i = 0;
  int j = 0;
  while (i < text.length()) {
    if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
      i++;
      j++;
      if (j == pattern.length()) {
        positions.add(i - j);
        j = next[j];
      }
    } else {
      j = next[j];
    }
  }
  return positions;
}

使用以上代码，我们可以找到指定字符串中所有的子串。下面是一个使用示例：


public static void main(String[] args) {
  Solution solution = new Solution();
  String text = "ABABDABACDABABCABAB";
  String pattern = "ABABCABAB";
  List<Integer> positions = solution.findSubstring(text, pattern);
  
  if (positions.isEmpty()) {
    System.out.println("No matching substrings found.");
  } else {
    System.out.println("Matching substrings found at positions: " + positions);
  }
}

以上代码将输出：Matching substrings found at positions: [10]，表示在主串text中，模式串pattern在位置10处匹配。

总结：KMP算法是一种高效的字符串匹配算法，它通过建立部分匹配表来避免重复的比较操作。使用Java实现KMP算法可以非常方便地找到指定字符串中的所有子串。希望本文对于理解和应用KMP算法有所帮助。

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

下一篇: FFmpeg文件名：探索视频处理利器的命名规则和使用方法

评论区

()

相似文章