21xrx.com
2025-04-14 23:01:42 Monday
文章检索 我的文章 写文章
KMP算法Java实现
2023-09-17 15:02:46 深夜i     --     --
KMP算法 Java 实现

KMP算法是一种高效的字符串匹配算法，它的实现可以大大提高字符串匹配的效率。本文将介绍KMP算法的Java实现。

KMP算法是由Knuth-Morris-Pratt三位科学家于1977年提出的，它的核心思想是利用已经匹配过的部分信息来避免不必要的比较。

在KMP算法中，我们需要构建一个部分匹配表，这个表记录了每一个前缀串（除去第一个字符）中最长的相等前缀和后缀的长度。根据这个表，我们可以在匹配过程中遇到不匹配的字符时，直接跳过已经匹配的部分，从而提高匹配效率。

下面是KMP算法的Java实现代码：

public class KMP {
  public static int kmp(String text, String pattern) {
    int[] lps = computeLPSArray(pattern);
    int n = text.length();
    int m = pattern.length();
    int i = 0; // text中的指针
    int j = 0; // pattern中的指针
    while (i < n) {
      if (text.charAt(i) == pattern.charAt(j)) {
        i++;
        j++;
      }
      if (j == m)
        return i - j;
       else if (i < n && text.charAt(i) != pattern.charAt(j)) {
        if (j != 0)
          j = lps[j - 1];
        else
          i++;
      }
    }
    return -1;
  }
  private static int[] computeLPSArray(String pattern) {
    int m = pattern.length();
    int[] lps = new int[m];
    int len = 0;
    int i = 1;
    while (i < m) {
      if (pattern.charAt(i) == pattern.charAt(len)) {
        len++;
        lps[i] = len;
        i++;
      } else {
        if (len != 0) {
          len = lps[len - 1];
        } else {
          lps[i] = len;
          i++;
        }
      }
    }
    return lps;
  }
  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(String text, String pattern)方法接受两个参数，分别是待匹配的文本字符串和要搜索的模式字符串。该方法中，我们首先调用了computeLPSArray(String pattern)方法来构建部分匹配表。然后使用两个指针i和j分别指向text和pattern的起始位置，然后进行匹配过程。

在匹配过程中，如果text[i]和pattern[j]相等，我们就将两个指针都向后移动一位。如果j等于模式字符串的长度m，则表示找到了一个完整的匹配，返回起始位置的索引。如果text[i]和pattern[j]不相等，我们会移动模式指针j到lps[j-1]的位置，这个位置记录了最长相等前缀和后缀的长度，这样可以避免重复比较已经匹配过的部分。

在上述代码中，我们通过调用kmp方法来在文本字符串中搜索模式字符串，如果找到了匹配的子串，就会返回其起始位置的索引，否则返回-1。我们通过main方法来测试这个算法，在给定的文本字符串中搜索模式字符串，并打印出结果。

总之，KMP算法是一种高效的字符串匹配算法，其内部实现通过构建部分匹配表来提高匹配效率。通过使用KMP算法，我们可以更加高效地在字符串中搜索目标模式。通过这篇文章，我们了解了KMP算法的Java实现，并通过一个简单的示例进行了演示。

  
  

评论区