KMP算法Java实现 |21xrx.com

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算法，我们可以快速地在一个主串中匹配一个模式串，提高了字符串匹配的效率。

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

下一篇: C语言中const的使用

评论区

相似文章