21xrx.com
2025-03-30 02:43:47 Sunday
文章检索 我的文章 写文章
KMP算法Java代码实现
2023-09-15 19:25:21 深夜i     17     0
KMP算法 Java代码 实现

KMP算法是一种用于在一个较长字符串中检索一个较短字符串的高效算法。通过利用已匹配的部分字符，KMP算法能够避免不必要的比较，从而提高搜索的效率。在Java中，我们可以使用以下代码来实现KMP算法。

public class KMP {
  public static int search(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] lps = new int[m];
    computeLPSArray(pattern, m, lps);
    
    int i = 0; // text中的索引
    int j = 0; // pattern中的索引
    while (i < n) {
      if (pattern.charAt(j) == text.charAt(i)) {
        i++;
        j++;
      }
      if (j == m)
        return i - j;
      
      else if (i < n && pattern.charAt(j) != text.charAt(i)) {
        if (j != 0) {
          j = lps[j - 1];
        }
        else {
          i++;
        }
      }
    }
    return -1; // 没有找到匹配的子串
  }
  
  private static void computeLPSArray(String pattern, int m, int[] lps) {
    int len = 0; // 结束于lps[i]的前缀的长度
    int i = 1;
    lps[0] = 0;
    
    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] = len;
          i++;
        }
      }
    }
  }
  
  public static void main(String[] args) {
    String text = "ABCABCDABABCDABCDABDE";
    String pattern = "ABCDABD";
    int index = search(text, pattern);
    if (index != -1) {
      System.out.println("Pattern found at index " + index);
    }
    else {
      System.out.println("Pattern not found");
    }
  }
}

上述代码实现了KMP算法的核心逻辑。在search方法中，我们使用两个指针i和j来遍历text和pattern字符串，同时使用lps数组来存储pattern子串中的最长公共前后缀的长度。通过不断地更新i和j的值，我们最终可以找到pattern在text中的起始位置。

在computeLPSArray方法中，我们计算出lps数组的值。通过迭代比较pattern中的字符，我们逐步更新lps数组，以便在搜索过程中进行快速回退。

在main方法中，我们定义了一个示例的text和pattern，并调用search方法来查找pattern在text中的位置。如果找到了匹配的子串，则输出其起始索引；否则，输出未找到。

总之，KMP算法是一种高效的字符串搜索算法，在Java语言中可以通过以上代码实现。通过利用已匹配的部分字符，KMP算法能够提高搜索的效率，尤其在处理长字符串时表现更加出色。

  
  

评论区

请求出错了