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

KMP算法Java代码解析

2023-10-27 10:30:19 深夜i -- --

KMP算法 Java代码解析

KMP算法是一种用于字符串匹配的高效算法。它的全称是Knuth-Morris-Pratt算法，是由Donald Knuth、Vaughan Pratt和James Morris三位计算机科学家在上世纪70年代提出的。

KMP算法的主要思想是利用模式串自身的特点来提前确定每次匹配失败时，模式串需要移动的位置。这样可以减少不必要的字符比较，提高匹配效率。

下面是一段使用Java语言实现的KMP算法代码解析。


public class KMP {
  public static int kmpSearch(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] lps = calculateLPS(pattern);
    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 (j != 0) {
          j = lps[j - 1];
        } else {
          i++;
        }
      }
    }
    return -1; // 匹配失败
  }
  private static int[] calculateLPS(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] = 0;
          i++;
        }
      }
    }
    return lps;
  }
  public static void main(String[] args) {
    String text = "ABCABDABACDABABCABDA";
    String pattern = "ABABCABD";
    int index = kmpSearch(text, pattern);
    if (index != -1) {
      System.out.println("匹配成功，起始位置为：" + index);
    } else {
      System.out.println("匹配失败");
    }
  }
}

上面的代码首先定义了一个静态方法`kmpSearch`，用于执行KMP算法的搜索过程。方法接收一个文本串`text`和一个模式串`pattern`作为输入，并返回模式串在文本串中的起始位置。如果匹配失败，则返回-1。

在`kmpSearch`方法内部，首先通过调用`calculateLPS`方法计算模式串的最长公共前后缀数组`lps`。然后使用两个索引`i`和`j`分别指向文本串和模式串的起始位置。

接下来，通过一个`while`循环来遍历文本串。在循环中，如果当前字符相等，则逐个比较下一个字符。如果`j`等于模式串的长度`m`，则说明匹配成功，返回当前位置减去模式串长度的值。

如果当前字符不相等，则根据`lps`数组来更新`j`的值。如果`j`不等于0，则将`j`设置为`lps[j-1]`，继续比较当前字符和模式串中的下一个字符。如果`j`等于0，则直接将文本串的索引`i`加1。

最后，在`main`方法中使用一个示例文本串和模式串进行测试，并根据匹配结果输出相应的提示信息。

总之，KMP算法是一种高效的字符串匹配算法，通过利用模式串自身的特点来提前确定每次匹配失败时模式串的移动位置，从而减少字符比较的次数。使用Java语言实现KMP算法的代码可以帮助我们更好地理解和应用该算法。

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

下一篇: 使用FFmpeg进行视频文件的快速剪辑

评论区

()

相似文章