KMP算法的JAVA代码实现 |21xrx.com

KMP算法的JAVA代码实现

2023-10-14 16:17:36 深夜i -- --

KMP算法 JAVA代码实现

KMP算法是一种高效的字符串匹配算法，它利用了字符串相同子串的重复性质，减少了不必要的比较次数，从而提高了匹配效率。下面是一个使用JAVA语言实现KMP算法的代码示例。


public class KMP {
  public static int kmp(String txt, String pattern) {
    int[] lps = computeLPSArray(pattern);
    int i = 0; // txt的指针
    int j = 0; // pattern的指针
    while (i < txt.length()) {
      if (pattern.charAt(j) == txt.charAt(i)) {
        j++;
        i++;
      }
      if (j == pattern.length())
        return i - j;
       else if (i < txt.length() && pattern.charAt(j) != txt.charAt(i)) {
        if (j != 0) {
          j = lps[j - 1];
        } else {
          i++;
        }
      }
    }
    return -1;
  }
  private static int[] computeLPSArray(String pattern) {
    int[] lps = new int[pattern.length()];
    int len = 0;
    int i = 1;
    while (i < pattern.length()) {
      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++;
        }
      }
    }
    return lps;
  }
  public static void main(String[] args) {
    String txt = "ababcabcabababd";
    String pattern = "abcabab";
    int index = kmp(txt, pattern);
    if (index != -1) {
      System.out.println("Pattern found at index " + index);
    } else {
      System.out.println("Pattern not found");
    }
  }
}

这段代码实现了KMP算法的逻辑。首先，通过调用computeLPSArray函数，生成pattern字符串的最长公共前后缀数组lps。然后，在kmp函数中，使用i和j作为txt和pattern的指针，并进行比较。如果当前字符匹配，i和j都向后移动一位；如果当前字符不匹配，j回退到lps[j - 1]的位置，继续与txt进行比较。最后，如果j等于pattern.length()，说明找到了匹配的子串，返回其起始位置；否则，返回-1表示没有找到匹配的子串。

通过运行main函数，可以看到输出结果为"Pattern found at index 2"，即在txt字符串中找到了匹配pattern的子串，起始位置为2。

KMP算法的时间复杂度为O(m + n)，其中m为txt的长度，n为pattern的长度。相比暴力匹配算法的O(m * n)时间复杂度，KMP算法在字符串匹配中具有较高的效率和性能。

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

下一篇: Java开发常用的日语技术词汇

评论区

()

相似文章