Java程序实现KMP算法 |21xrx.com

Java程序实现KMP算法

2023-09-10 11:14:53 深夜i 15 0

Java程序 KMP算法字符串匹配前缀表模式串

KMP算法是一种字符串匹配算法，它的全称是Knuth-Morris-Pratt算法。该算法最早由Donald Knuth、Vaughan Pratt和James Morris于1977年提出。KMP算法的核心思想是利用已经匹配过的信息来尽量减少不必要的字符比较，从而提高匹配的效率。

在Java程序中，我们可以很容易地实现KMP算法。

首先，我们需要实现一个辅助函数，该函数负责生成一个用于匹配的部分字符匹配表。该表记录了字符串前缀和后缀的最长公共部分的长度。通过计算该表，可以在匹配过程中不用重复比较已经匹配过的字符。

下面是一个示例的KMP算法实现：

public class KMPAlgorithm {
  public static int[] buildTable(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)) {
        table[i] = ++j;
      } else {
        if (j != 0) {
          j = table[j - 1];
          i--;
        }
      }
    }
    return table;
  }
  public static int search(String text, String pattern) {
    int[] table = buildTable(pattern);
    int j = 0;
    for (int i = 0; i < text.length(); i++) {
      if (text.charAt(i) == pattern.charAt(j)) {
        j++;
        if (j == pattern.length()) {
          return i - j + 1;
        }
      } else {
        if (j != 0) {
          j = table[j - 1];
          i--;
        }
      }
    }
    return -1;
  }
  public static void main(String[] args) {
    String text = "ABCABCDABABCDABCDABDE";
    String pattern = "ABCDABD";
    int result = search(text, pattern);
    System.out.println("Pattern found at index: " + result);
  }
}

在上述示例中，我们首先通过`buildTable`函数来生成部分字符匹配表。然后，在`search`函数中，我们根据生成的表进行字符串匹配。最后，在`main`函数中，我们通过调用`search`函数来进行匹配，并打印出匹配结果的索引。

通过上述Java程序，我们可以很方便地实现KMP算法。该算法在字符串匹配中具有较高的效率，特别是当匹配的字符串较长时，KMP算法相比于传统的暴力匹配算法具有明显的优势。因此，在实际的开发中，KMP算法经常被使用来解决字符串匹配的问题。

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

下一篇: 工业中极少使用opencv进行应用

评论区

相似文章