21xrx.com
2025-03-16 10:56:40 Sunday
文章检索 我的文章 写文章
KMP算法Java实现
2023-08-22 10:40:15 深夜i     16     0
KMP算法 Java实现 字符串匹配 失配函数 前缀后缀匹配

KMP算法,全称为Knuth-Morris-Pratt算法,是一种字符串匹配算法。它可以在一个主串中快速匹配一个模式串,时间复杂度为O(n+m),其中n是主串的长度,m是模式串的长度。

KMP算法的实现可以使用Java语言来完成。首先需要在代码中定义一个getNext函数,用于生成模式串的前缀表。前缀表是一个数组,其中存储了每个位置上的最长公共前后缀的长度。

然后,在主函数中,我们需要定义一个字符串变量text,表示主串,以及一个字符串变量pattern,表示模式串。接下来,我们可以调用getNext函数生成模式串的前缀表。

在匹配过程中,我们需要使用两个指针i和j来分别指向主串和模式串。当两个字符匹配时,我们将两个指针都向后移动一位。如果不匹配,则根据前缀表来移动模式串的指针j,同时保持主串的指针i不动。这样可以避免不必要的比较,提高匹配速度。

具体的代码实现可以参考下面的示例:

public class KMPAlgorithm {
  public static 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 static 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;
    
    return -1;
  }
  public static void main(String[] args) {
    String text = "ABABDABACDABABCABAB";
    String pattern = "ABABCABAB";
    int index = kmp(text, pattern);
    if (index != -1) {
      System.out.println("Pattern found at index " + index);
    } else {
      System.out.println("Pattern not found");
    }
  }
}

以上就是KMP算法的Java实现。通过使用KMP算法,我们可以快速地在一个主串中匹配一个模式串,提高了字符串匹配的效率。

  
  

评论区

请求出错了