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

Java实现KMP算法的代码

2023-08-08 11:56:27 深夜i -- --

Java KMP算法代码实现

KMP算法是一种用于字符串匹配的高效算法。其原理是在模式串与目标串之间进行匹配时，通过预处理模式串来实现跳过已匹配过的字符，从而减少比较次数，提高匹配效率。在Java中，我们可以利用KMP算法来实现字符串匹配。

下面是使用Java实现KMP算法的示例代码：


public class KMP {
  private static int[] calculateLPS(String pattern) {
    int[] lps = new int[pattern.length()];
    int i = 0, j = 1;
    while (j < pattern.length()) {
      if (pattern.charAt(i) == pattern.charAt(j)) {
        lps[j] = i + 1;
        i++;
        j++;
      } else {
        if (i != 0) {
          i = lps[i - 1];
        } else {
          lps[j] = 0;
          j++;
        }
      }
    }
    return lps;
  }
  public static int search(String text, String pattern) {
    int[] lps = calculateLPS(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 = lps[j - 1];
        } else {
          i++;
        }
      }
    }
    if (j == pattern.length())
      return i - j;
    
    return -1;
  }
  public static void main(String[] args) {
    String text = "ABABDABACDABABCABAB";
    String pattern = "ABABCABAB";
    int index = search(text, pattern);
    if (index == -1) {
      System.out.println("Pattern not found in the given text");
    } else {
      System.out.println("Pattern found at index " + index);
    }
  }
}

这段代码实现了KMP算法的主要逻辑。首先，我们通过`calculateLPS`方法对模式串进行预处理，得到最长公共前后缀数组`lps`。然后，我们使用`search`方法在目标字符串中搜索匹配的模式串。最后，在`main`方法中，我们提供了一个示例来演示如何使用这个KMP算法。

这段代码的时间复杂度为O(n + m)，其中n是目标字符串的长度，m是模式串的长度。经过预处理，KMP算法能够实现更快速的字符串匹配，适用于大规模文本搜索和数据处理等应用场景。

总而言之，KMP算法是一种高效的字符串匹配算法，通过使用Java语言实现，我们可以轻松应用它来解决实际问题。希望这个示例代码对您理解KMP算法和其在Java中的应用有所帮助。

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

下一篇: C#中异常处理语句的使用方法

评论区

()

相似文章