Java实现KMP算法的代码 |21xrx.com

Java实现KMP算法的代码

2023-08-13 20:29:04 深夜i -- --

Java KMP算法实现代码

KMP（Knuth-Morris-Pratt）算法是一种字符串匹配算法，用于在一个字符串（称为主串）中查找另一个字符串（称为模式串）的出现位置。相比于朴素的字符串匹配算法，KMP算法具有更高的效率和更低的时间复杂度。在Java中，我们可以使用以下代码来实现KMP算法：


public class KMP {
  public static int kmp(String s, String p) {
    int n = s.length();
    int m = p.length();
    int[] next = getNext(p);
    int i = 0;
    int j = 0;
    while (i < n && j < m) {
      if (j == -1 || s.charAt(i) == p.charAt(j)) {
        i++;
        j++;
      } else {
        j = next[j];
      }
    }
    if (j == m)
      return i - j;
     else
      return -1;
    
  }
  private static int[] getNext(String p) {
    int m = p.length();
    int[] next = new int[m];
    next[0] = -1;
    int i = 0;
    int j = -1;
    while (i < m - 1) {
      if (j == -1 || p.charAt(i) == p.charAt(j)) {
        i++;
        j++;
        next[i] = j;
      } else {
        j = next[j];
      }
    }
    return next;
  }
  public static void main(String[] args) {
    String s = "ABCABABCDABABCDABCDABDE";
    String p = "ABCDABD";
    int index = kmp(s, p);
    if (index != -1) {
      System.out.println("Pattern found at index " + index);
    } else {
      System.out.println("Pattern not found");
    }
  }
}

在上述代码中，我们定义了一个KMP类，其中包含了一个kmp方法和一个getNext方法。kmp方法用于在主串s中查找模式串p的出现位置，getNext方法用于计算模式串p的next数组。

在kmp方法中，我们首先获取主串s和模式串p的长度。然后，我们定义两个指针i和j分别指向主串和模式串的起始位置。

在一个循环中，我们比较主串s和模式串p中相应位置的字符。如果字符相等，则两个指针同时向后移动一位；如果字符不相等，则通过next数组找到j指针应该跳转的位置。

在getNext方法中，我们首先获取模式串p的长度，并创建一个大小为m的数组next。然后，我们定义两个指针i和j分别指向模式串的起始位置和前缀位置。

在一个循环中，我们比较模式串p中i和j位置的字符。如果字符相等，则两个指针同时向后移动一位，并将next[i+1]的值更新为j+1；如果字符不相等，则通过next数组找到j指针应该跳转的位置。

最后，我们在main方法中定义了一个主串s和一个模式串p，并调用kmp方法来查找模式串p在主串s中的出现位置。如果返回的结果不为-1，则说明模式串p在主串s中存在；否则，模式串p在主串s中不存在。

以上就是使用Java实现KMP算法的代码。这段代码非常简洁并且易于理解，它可以在较短的时间内有效地完成字符串匹配任务。KMP算法在实际的软件开发中广泛应用，特别是在文本编辑、搜索引擎和模式识别等领域。

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

下一篇: 使用OpenCV调用YOLOv7进行目标检测

评论区

()

相似文章