KMP算法Java实现——博客园详解 |21xrx.com

KMP算法Java实现——博客园详解

2023-09-27 21:41:21 深夜i -- --

KMP算法 Java实现博客园详解

KMP算法是一种字符串匹配算法，用于在一个主字符串中寻找一个模式字符串的出现位置。它的基本思想是，当一个字符无法匹配时，不需要从头开始重新匹配，而是利用已经匹配过的部分，通过一些特殊的计算，将模式字符串向后移动一定的位置，以减少比较的次数，从而提高匹配的效率。

在Java中，我们可以通过编写一个KMP类来实现KMP算法。下面是一个详细的实现步骤。

首先，我们需要定义一个getNext函数，用于计算模式字符串的部分匹配表。部分匹配表是一个数组，记录了模式字符串中每个位置对应的最长相同前后缀的长度。


private 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;
}

然后，我们可以编写一个kmp函数，用于在主字符串中寻找模式字符串的位置。该函数利用getNext函数计算模式字符串的部分匹配表，并通过比较字符来移动模式字符串的位置。


public 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;
  
}

最后，我们可以调用kmp函数来进行测试。


public static void main(String[] args) {
  String text = "ABABABABCD";
  String pattern = "ABABC";
  KMP kmp = new KMP();
  int position = kmp.kmp(text, pattern);
  if (position != -1) {
    System.out.println("Pattern found at position " + position);
  } else {
    System.out.println("Pattern not found");
  }
}

运行结果为：

Pattern found at position 2

通过KMP算法，我们可以在主字符串中快速寻找模式字符串的位置，大大提高了字符串匹配的效率。在实际应用中，KMP算法被广泛使用，例如在文本搜索、字符串替换等场景中。通过掌握KMP算法的原理和Java实现方式，我们可以更加高效地处理字符串匹配问题。

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

下一篇: 使用OpenCV调用摄像头采集图像

评论区

()

相似文章