Java实现KMP算法 |21xrx.com

Java实现KMP算法

2023-09-22 02:17:46 深夜i -- --

Java KMP算法字符串匹配子串查找字符比较

KMP算法，即Knuth-Morris-Pratt算法，是一种高效的字符串匹配算法，用于在一个文本中查找一个模式串是否出现。相比于朴素的字符串匹配算法，KMP算法时间复杂度更低，可以大大提高字符串匹配的效率。在Java中，我们可以很方便地实现KMP算法。

KMP算法的核心思想是利用部分匹配表（Partial Match Table）来减小匹配过程中的回溯次数。部分匹配表是一个关于模式串的数组，记录了模式串中每个前缀的最长的相等前缀后缀的长度。在匹配过程中，当出现不匹配的字符时，我们可以根据部分匹配表的信息将模式串向右移动若干位，而无需回溯到文本开始的位置，从而提高匹配效率。

在Java中实现KMP算法的关键是构建部分匹配表，然后利用该表进行匹配。首先，我们需要定义一个用于构建部分匹配表的方法，它接受一个模式串作为参数，并返回一个部分匹配表。构建部分匹配表的方法如下：


private static int[] buildPartialMatchTable(String pattern) {
  int[] table = new int[pattern.length()];
  int j = 0;
  for (int i = 1; i < pattern.length(); i++) {
    if (pattern.charAt(i) == pattern.charAt(j)) {
      j++;
      table[i] = j;
    } else {
      if (j != 0) {
        j = table[j - 1];
        i--;
      }
    }
  }
  return table;
}

然后，我们可以定义一个用于进行字符串匹配的方法，它接受一个文本和一个模式串作为参数，并返回模式串在文本中的起始位置。匹配方法如下：


public static int kmpSearch(String text, String pattern) {
  int[] table = buildPartialMatchTable(pattern);
  int i = 0;
  int j = 0;
  while (i < text.length()) {
    if (text.charAt(i) == pattern.charAt(j)) {
      i++;
      j++;
      if (j == pattern.length())
        return i - j;
      
    } else {
      if (j != 0) {
        j = table[j - 1];
      } else {
        i++;
      }
    }
  }
  return -1;
}

通过调用kmpSearch方法，我们可以很方便地实现KMP算法来进行字符串匹配。例如，我们可以使用以下代码进行测试：


public static void main(String[] args) {
  String text = "ABCABCDABABCDABCDABDE";
  String pattern = "ABCDABD";
  int index = kmpSearch(text, pattern);
  if (index != -1) {
    System.out.println("Pattern found at index " + index);
  } else {
    System.out.println("Pattern not found");
  }
}

上述代码输出的结果是"Pattern found at index 8"，表明模式串 "ABCDABD" 在文本 "ABCABCDABABCDABCDABDE" 中的起始位置是8。

总结来说，Java中实现KMP算法的步骤是首先构建部分匹配表，然后利用该表进行字符串匹配。KMP算法是一种高效的字符串匹配算法，在处理大规模文本匹配时能够提供较好的效率。通过在Java中实现KMP算法，我们可以方便地完成字符串匹配的任务。

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

下一篇: C++中freopen函数的用法详解

评论区

()

相似文章