KMP算法Java实现 |21xrx.com

KMP算法Java实现

2023-10-29 03:56:20 深夜i -- --

KMP算法 Java实现字符串匹配模式匹配字符串搜索

KMP算法是一种非常高效的字符串匹配算法，在处理大量字符串匹配的情况下效果显著。今天我们来学习一下KMP算法的Java实现。

KMP算法的全称是Knuth-Morris-Pratt算法，它的主要思想是利用已经匹配过的部分字符信息，跳过一些不必要的比较操作，从而加快字符串匹配的速度。相比于传统的字符串匹配方法，KMP算法具有线性的时间复杂度，因此非常适用于处理大规模的字符串匹配问题。

那么，我们来看一下KMP算法的实现过程。

首先，我们需要创建一个辅助数组next[]，用来存储模式串中每个字符对应的最长可匹配前缀子串的下一个字符位置。这个数组的构建是KMP算法的核心。

接下来，我们需要编写一个函数来构建这个辅助数组。下面是KMP算法的Java实现代码：


public class KMP {
  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;
  }
  
  public int kmp(String text, String pattern) {
    int i = 0, j = 0;
    int[] next = getNext(pattern);
    
    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;
    
  }
  
  public static void main(String[] args) {
    KMP kmp = new KMP();
    String text = "ABABABABCABABABAB";
    String pattern = "ABABABC";
    int index = kmp.kmp(text, pattern);
    if (index != -1) {
      System.out.println("Pattern found at index " + index);
    } else {
      System.out.println("Pattern not found");
    }
  }
}

在上面的代码中，我们首先在主函数中创建了一个KMP对象，并定义了一个用于测试的文本字符串和模式字符串。然后，我们调用kmp()函数来进行字符串匹配。

在kmp()函数中，我们首先调用getNext()函数来构建辅助数组next[]。然后，我们使用两个指针i和j来遍历文本和模式字符串，并进行比较。如果当前字符匹配成功，则继续比较下一个字符；如果当前字符匹配失败，则根据辅助数组next[]来跳过一些比较操作。

最后，我们根据j是否等于模式字符串的长度来判断是否找到了匹配的子串。如果j等于模式字符串的长度，则找到了匹配的子串，并返回其起始位置；否则，没有找到匹配的子串，并返回-1。

运行上面的代码，我们会得到如下的输出结果：

Pattern found at index 6

这说明，在文本字符串中找到了模式字符串，并且它的起始位置是6。

综上所述，KMP算法是一种高效的字符串匹配算法，我们通过Java实现了它。希望通过这篇文章的介绍，您对KMP算法的实现有了更深入的了解。如果您需要处理大规模字符串匹配问题，KMP算法会是您的良好选择。

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

下一篇: 使用OpenCV的find_package方法找到库

评论区

()

相似文章