21xrx.com
2024-11-22 03:27:22 Friday
登录
文章检索 我的文章 写文章
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中的应用有所帮助。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复