KMP算法Java代码解析与实现 |21xrx.com

KMP算法Java代码解析与实现

2023-07-26 18:35:59 深夜i 15 0

KMP算法 Java代码解析实现

KMP算法是一种常用的字符串匹配算法，可以快速地在一个字符串中查找某个子串的位置。下面将对KMP算法的Java代码进行解析与实现。

首先，KMP算法的核心思想是利用已经匹配过的信息，避免重复匹配。具体实现代码如下：

public class KMPAlgorithm {
 
  public static int KMP(String str, String pattern) {
    int[] next = generateNext(pattern); //生成next数组
    int i = 0, j = 0;
    while (i < str.length() && j < pattern.length()) {
      if (j == -1 || str.charAt(i) == pattern.charAt(j)) {
        i++;
        j++;
      } else {
        j = next[j];
      }
    }
    if (j == pattern.length())
      return i - j;
    
    return -1;
  }
 
  public static int[] generateNext(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 void main(String[] args) {
    String str = "ABC ABCDAB ABCDABCDABDE";
    String pattern = "ABCDABD";
    int index = KMP(str, pattern);
    if (index != -1) {
      System.out.println("匹配成功，子串位置为：" + index);
    } else {
      System.out.println("未找到匹配的子串");
    }
  }
}

以上代码中的KMP方法是主要的匹配函数，该函数使用两个指针`i`和`j`在字符串中进行遍历匹配。`next`数组用于存储每个匹配失败时，下一次匹配应该从哪个位置开始。在匹配过程中，如果当前字符匹配成功，则`i`和`j`继续向下移动；如果不匹配，则根据`next`数组中保存的位置进行回溯。最后，如果`j`等于模式串的长度，表示匹配成功，否则返回-1表示未找到匹配的子串。

`generateNext`方法用于生成`next`数组。在遍历模式串的过程中，如果当前字符匹配成功，则继续向下移动；如果不匹配，则回到`j`所指向的位置重新开始匹配。

在`main`函数中，定义了一个待搜索的字符串`str`和一个模式串`pattern`，然后调用KMP方法进行匹配。如果匹配成功，则输出子串在字符串中的位置；如果未找到匹配的子串，则输出未找到的提示消息。

综上所述，通过以上的代码解析与实现，我们可以更加深入地理解KMP算法在字符串匹配中的应用。这个算法具有时间复杂度为O(n+m)的优势，其中n为字符串长度，m为模式串长度，因此非常高效。在实际应用中，KMP算法可以用于字符串搜索、文本编辑器等多个领域。

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

下一篇: Java排序的使用方法

评论区

相似文章