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

使用Java实现KMP算法的代码

2023-09-23 16:33:10 深夜i 16 0

Java KMP算法实现代码

KMP算法是一种用于字符串匹配的有效算法，它能够在一个主文本字符串中查找一个模式字符串的出现位置。KMP算法的原理是根据模式字符串的前缀和后缀的匹配情况，在匹配失败时，避免不必要的回溯，提高匹配效率。

在Java中，我们可以使用以下代码实现KMP算法：

public class KMP {
  
  public static int match(String text, String pattern) {
    // 预处理模式字符串，构建next数组
    int[] next = computeNext(pattern);
    
    int i = 0; // 主文本字符串的指针
    int j = 0; // 模式字符串的指针
    
    while (i < text.length()) {
      // 当匹配成功时，两个指针同时后移
      if (text.charAt(i) == pattern.charAt(j)) {
        i++;
        j++;
      }
      
      // 当匹配失败时，根据next数组进行模式字符串的回溯
      if (j == pattern.length())
        return i - j; // 返回匹配的起始位置
      
      
      if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
        if (j != 0) {
          j = next[j - 1]; // 根据next数组回溯
        } else {
          i++; // 主文本字符串指针后移
        }
      }
    }
    
    return -1; // 未找到匹配的位置
  }
  
  private static int[] computeNext(String pattern) {
    int[] next = new int[pattern.length()];
    int j = 0;
    
    for (int i = 1; i < pattern.length(); i++) {
      if (pattern.charAt(i) == pattern.charAt(j)) {
        j++;
        next[i] = j;
      } else {
        if (j != 0) {
          j = next[j - 1]; // 根据next数组回溯
          i--; // 模式字符串指针不变，继续判断
        } else {
          next[i] = 0;
        }
      }
    }
    
    return next;
  }
  public static void main(String[] args) {
    String text = "ABCDABCDABDE";
    String pattern = "ABDE";
    
    int index = match(text, pattern);
    
    if (index == -1) {
      System.out.println("Pattern not found!");
    } else {
      System.out.println("Pattern found at index " + index);
    }
  }
}

在上面的代码中，我们定义了一个`KMP`类，并实现了一个`match`方法来进行字符串匹配。该方法接受两个字符串作为参数：`text`表示主文本字符串，`pattern`表示模式字符串。在匹配时，我们使用两个指针`i`和`j`来分别遍历主文本字符串和模式字符串。通过比较字符是否相等，确定是否匹配。

如果匹配失败，我们根据模式字符串的前缀和后缀的匹配情况，在`j`不等于0时，通过查找`next`数组来回溯模式字符串的指针`j`。同时，我们在构建`next`数组时，优化了匹配失败时的回溯操作。最后，返回匹配的起始位置或者-1表示未找到匹配的位置。

在`main`方法中，我们通过调用`match`方法来测试KMP算法的实现。定义了一个主文本字符串`text`和一个模式字符串`pattern`。根据匹配结果，输出相关信息。

通过以上实现代码，我们可以使用Java来实现KMP算法进行字符串匹配，提高匹配效率，加快程序的执行速度。

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

下一篇: OpenCV绘制曲线图的实现方法

评论区

相似文章