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

KMP算法Java代码实例

2023-09-14 20:39:54 深夜i -- --

KMP算法 Java代码实例匹配

KMP算法是一种字符串匹配算法，它的核心思想是利用已经部分匹配的信息，尽量减少不必要的字符比较，从而提高匹配的效率。在 Java 中，我们可以使用以下代码实现 KMP 算法。


import java.util.Arrays;
public class KMPAlgorithm {
  public static int[] generateTable(String pattern) {
    int[] table = new int[pattern.length()];
    int j = 0;
    for (int i = 1; i < pattern.length(); i++) {
      if (pattern.charAt(i) == pattern.charAt(j)) {
        table[i] = j + 1;
        j++;
      } else {
        if (j != 0) {
          j = table[j - 1];
          i--;
        } else {
          table[i] = 0;
        }
      }
    }
    return table;
  }
  public static int indexOf(String text, String pattern) {
    int[] table = generateTable(pattern);
    int i = 0, j = 0;
    while (i < text.length() && j < pattern.length()) {
      if (text.charAt(i) == pattern.charAt(j)) {
        i++;
        j++;
      } else {
        if (j != 0) {
          j = table[j - 1];
        } else {
          i++;
        }
      }
    }
    if (j == pattern.length())
      return i - j;
    
    return -1;
  }
  public static void main(String[] args) {
    String text = "ABCABCDABCABD";
    String pattern = "ABCABD";
    int index = indexOf(text, pattern);
    if (index != -1) {
      System.out.println("Pattern found at index " + index);
    } else {
      System.out.println("Pattern not found");
    }
  }
}

以上是一个基于 KMP 算法的字符串匹配示例，其中 `generateTable` 方法用于生成部分匹配表，使用动态规划的思想。`indexOf` 方法用于在给定文本中查找模式字符串，返回匹配的起始索引，若找不到则返回 -1。在 `main` 方法中，我们定义了一个文本字符串和一个模式字符串，并通过 `indexOf` 方法进行匹配。

通过 KMP 算法，我们可以有效地在文本中进行字符串匹配。它的时间复杂度为 O(n+m)，其中 n 是文本的长度，m 是模式字符串的长度。相比暴力匹配法的时间复杂度 O(n*m)，KMP 算法具有更优秀的性能表现。因此，在实际的软件开发中，KMP 算法被广泛应用于字符串匹配问题的解决。

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

下一篇: 使用FFmpeg将FLV转换为H.265编码

评论区

()

相似文章