KMP算法Java实现：详解及示例代码 |21xrx.com

KMP算法Java实现：详解及示例代码

2023-10-14 09:52:08 深夜i -- --

KMP算法 Java实现详解示例代码字符串匹配

KMP算法是一种用于字符串匹配的算法，通过巧妙地利用已经匹配过的前缀信息，来避免不必要的比较操作，提高了字符串匹配的效率。在本文中，我们将详细解释KMP算法的原理，并提供KMP算法的Java示例代码。

KMP算法的原理是基于一个观察：当在字符串中寻找一个子串时，如果该子串中的一部分字符与目标字符串匹配失败，我们可以利用已经匹配成功的前缀信息，使得匹配失败的字符位置不需要重新开始。这一观察推导出了KMP算法的核心思想——避免回溯。

KMP算法主要包含两个部分：第一部分是构建最大匹配数表（即next数组），第二部分是利用最大匹配数表进行字符串匹配。

首先，我们需要构建最大匹配数表。这个表记录了在匹配过程中，字符串被移动时应该跳过的位置。为了构建这个表，我们需要遍历目标字符串，并计算每个位置上的最大匹配数。具体方法如下：

1. 初始化一个数组next，其长度为目标字符串的长度+1，用于保存每个位置上的最大匹配数。

2. 设置两个指针i和j，分别指向目标字符串和子串的初始位置。

3. 在遍历目标字符串的过程中，如果字符匹配成功，则i和j都向后移动一位；如果匹配失败，则根据已匹配部分的最大匹配数来移动指针j（即j=next[j]）。

4. 在每次移动指针j后，将当前位置上的最大匹配数保存到next[i]中，并将i后移一位。

5. 重复上述步骤，直到遍历完整个目标字符串。

构建最大匹配数表完成后，接下来就可以使用这个表进行字符串匹配了。具体方法如下：

1. 设置两个指针i和j，分别指向目标字符串和子串的初始位置。

2. 在遍历目标字符串的过程中，如果字符匹配成功，则i和j都向后移动一位；如果匹配失败，则根据已匹配部分的最大匹配数来移动指针j（即j=next[j]）。

3. 如果j的值等于子串的长度，则表示匹配成功，返回在目标字符串中的起始位置；否则，继续遍历目标字符串。

4. 重复上述步骤，直到遍历完整个目标字符串。

下面是KMP算法的Java示例代码：


public class KMPAlgorithm {
  public static int kmp(String target, String pattern) {
    int i = 0;
    int j = 0;
    int[] next = getNextArray(pattern);
    while (i < target.length() && j < pattern.length()) {
      if (j == -1 || target.charAt(i) == pattern.charAt(j)) {
        i++;
        j++;
      } else {
        j = next[j];
      }
    }
    
    if (j == pattern.length())
      return i - j;
     else
      return -1;
    
  }
  private static int[] getNextArray(String pattern) {
    int[] next = new int[pattern.length()];
    next[0] = -1;
    int i = 0;
    int 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 target = "ABCABDABACDABABCABDE";
    String pattern = "ABABCABDE";
    int result = kmp(target, pattern);
    System.out.println("Pattern found at index: " + result);
  }
}

在上面的示例代码中，我们定义了一个kmp()方法，该方法接受目标字符串和子串作为参数，并返回子串在目标字符串中的起始位置。在main()方法中，我们使用了一个字符串来测试kmp()方法，并输出了结果。

总结：KMP算法是一种高效的字符串匹配算法，通过构建最大匹配数表和利用该表进行字符串匹配，可以避免不必要的比较操作，提高字符串匹配的效率。使用Java语言实现KMP算法非常简单，只需要几行代码即可完成。如果您在实际应用中遇到需要字符串匹配的场景，不妨尝试使用KMP算法来提高匹配效率。

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

下一篇: 简单教程：如何使用OpenCV控制摄像头拍摄照片和视频

评论区

()

相似文章