KMP算法Java实现 |21xrx.com

KMP算法Java实现

2023-10-19 03:22:29 深夜i -- --

KMP算法 Java 实现

KMP算法是一种用于在字符串中查找子串的高效算法。它的名字来自于算法的三位发明者：Don Knuth、James H. Morris和Vaughan Pratt。

在传统的字符串匹配算法中，我们通常使用暴力法，即从主串的每个位置依次与子串进行匹配，如果匹配失败，则主串向后移动一个位置，重新开始匹配。这种算法的时间复杂度为O(n*m)，其中n是主串的长度，m是子串的长度。

KMP算法通过利用已经匹配过的部分信息，避免了不必要的比较。它的核心思想是根据子串的特点，构建一个部分匹配表，也叫做失效函数。这个表记录了每个位置对应的最长可以匹配的前缀子串的长度。

具体来说，KMP算法首先根据子串构建失效函数。然后，从主串的第一个位置开始，逐个与子串进行匹配。如果当前字符匹配成功，则继续下一个字符的匹配；如果匹配失败，则根据失效函数计算出模式串应该移动的位置。通过这种方式，KMP算法可以在O(n+m)的时间复杂度内完成字符串匹配。

下面是KMP算法的Java实现：


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

在上述代码中，getNext方法用于构建失效函数。其中，i是主串的下标，j是子串的下标。当子串的第i个字符与子串的第j个字符匹配时，i和j都增加1，同时将next[i]设置为j。如果匹配失败，则将j更新为next[j]。kmp方法用于执行字符串匹配。在每个位置，如果当前字符匹配成功，则移动到下一个位置；如果匹配失败，则根据失效函数计算移动的位置。

在使用KMP算法进行字符串匹配时，时间复杂度为O(n+m)，其中n是主串的长度，m是子串的长度。相较于传统的字符串匹配算法，KMP算法具有更高的效率和性能。

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

下一篇: 为什么计算机应该学习C语言和Java？

评论区

()

相似文章