KMP算法Java封装及使用指南 |21xrx.com

KMP算法Java封装及使用指南

2023-09-23 22:13:10 深夜i -- --

KMP算法 Java实现封装使用指南字符串匹配

KMP算法是一种字符串匹配算法，它可以在一个文本串中快速查找一个模式串的出现位置。该算法的时间复杂度为O(n+m)，其中n是文本串的长度，m是模式串的长度。在Java中，我们可以使用KMP算法解决字符串匹配问题。

首先，我们需要将KMP算法封装成一个类，以便在其他代码中可以方便地使用。下面是KMP类的基本实现：


public class KMP {
  private int[] lps;
  public int search(String text, String pattern) {
    int m = pattern.length();
    int n = text.length();
    lps = new int[m];
    computeLPSArray(pattern);
    int i = 0; // index for text
    int j = 0; // index for pattern
    while (i < n) {
      if (pattern.charAt(j) == text.charAt(i)) {
        j++;
        i++;
      }
      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 void computeLPSArray(String pattern) {
    int m = pattern.length();
    int len = 0;
    int i = 1;
    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] = 0;
          i++;
        }
      }
    }
  }
}

现在，我们可以使用KMP类来进行字符串匹配操作。以下是一个示例：


public class Main {
  public static void main(String[] args) {
    String text = "ABABDABACDABABCABAB";
    String pattern = "ABABCABAB";
    KMP kmp = new KMP();
    int index = kmp.search(text, pattern);
    if (index != -1) {
      System.out.println("Pattern found at index " + index);
    } else {
      System.out.println("Pattern not found");
    }
  }
}

在上面的示例中，我们先定义了一个文本串和一个模式串，然后创建了一个KMP对象。接下来，我们使用KMP对象的search方法在文本串中查找模式串。如果找到了模式串，就输出其在文本串中的索引；否则，输出"Pattern not found"。

总结起来，KMP算法是一种高效的字符串匹配算法，可以快速查找模式串在文本串中的出现位置。通过将KMP算法封装成一个类，我们可以在Java中方便地使用这一算法。通过上面的示例，我们可以了解到如何使用KMP算法进行字符串匹配操作。希望这篇文章对你学习KMP算法及其在Java中的应用有所帮助。

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

下一篇: OpenCV自适应功能在图像处理中的应用

评论区

()

相似文章