21xrx.com
2024-11-05 14:45:04 Tuesday
登录
文章检索 我的文章 写文章
KMP算法Java代码解析与实现
2023-07-26 18:35:59 深夜i     --     --
KMP算法 Java代码 解析 实现

KMP算法是一种常用的字符串匹配算法,可以快速地在一个字符串中查找某个子串的位置。下面将对KMP算法的Java代码进行解析与实现。

首先,KMP算法的核心思想是利用已经匹配过的信息,避免重复匹配。具体实现代码如下:


public class KMPAlgorithm {

 

  public static int KMP(String str, String pattern) {

    int[] next = generateNext(pattern); //生成next数组

    int i = 0, j = 0;

    while (i < str.length() && j < pattern.length()) {

      if (j == -1 || str.charAt(i) == pattern.charAt(j)) {

        i++;

        j++;

      } else {

        j = next[j];

      }

    }

    if (j == pattern.length())

      return i - j;

    

    return -1;

  }

 

  public static int[] generateNext(String pattern) {

    int[] next = new int[pattern.length()];

    next[0] = -1;

    int i = 0, j = -1;

    while (i < pattern.length() - 1) {

      if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {

        i++;

        j++;

        next[i] = j;

      } else {

        j = next[j];

      }

    }

    return next;

  }

 

  public static void main(String[] args) {

    String str = "ABC ABCDAB ABCDABCDABDE";

    String pattern = "ABCDABD";

    int index = KMP(str, pattern);

    if (index != -1) {

      System.out.println("匹配成功,子串位置为:" + index);

    } else {

      System.out.println("未找到匹配的子串");

    }

  }

}

以上代码中的KMP方法是主要的匹配函数,该函数使用两个指针`i`和`j`在字符串中进行遍历匹配。`next`数组用于存储每个匹配失败时,下一次匹配应该从哪个位置开始。在匹配过程中,如果当前字符匹配成功,则`i`和`j`继续向下移动;如果不匹配,则根据`next`数组中保存的位置进行回溯。最后,如果`j`等于模式串的长度,表示匹配成功,否则返回-1表示未找到匹配的子串。

`generateNext`方法用于生成`next`数组。在遍历模式串的过程中,如果当前字符匹配成功,则继续向下移动;如果不匹配,则回到`j`所指向的位置重新开始匹配。

在`main`函数中,定义了一个待搜索的字符串`str`和一个模式串`pattern`,然后调用KMP方法进行匹配。如果匹配成功,则输出子串在字符串中的位置;如果未找到匹配的子串,则输出未找到的提示消息。

综上所述,通过以上的代码解析与实现,我们可以更加深入地理解KMP算法在字符串匹配中的应用。这个算法具有时间复杂度为O(n+m)的优势,其中n为字符串长度,m为模式串长度,因此非常高效。在实际应用中,KMP算法可以用于字符串搜索、文本编辑器等多个领域。

  
  

评论区

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