Java怎么实现KMP算法

本篇内容主要讲解"Java怎么实现KMP算法"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"Java怎么实现KMP算法"吧!

KMP 算法

KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图:

举个例子 (字符串 "abcabcdef" 匹配字符串 "abcdef"):

部分匹配表

部分匹配表 (Partial Match Table) 指的是 "前缀" 和 "后缀" 的最长共有元素的长度.

举个例子, 字符串 "ABCDABD" 的前缀与后缀:

KMP 算法实现

重点:

KMP 算法中移动的位数 = 已匹配的字符数 - 对应的部分匹配值

import java.util.Arrays;public class KMPMatch {    public static int Match(String str1, String str2, int[] next) {        // 初始化索引        int i = 0;        int j = 0;        for (; i < str1.length(); i++) {            if (j > 0 && str1.charAt(i) != str2.charAt(j)) {                // 不匹配, 回退                i = i - next[j - 1];                j = 0;            }            // 匹配            if (str1.charAt(i) == str2.charAt(j)) {                j++;            }            // 返回索引            if (j == str2.length()) {                return i - j + 1;            }        }        return -1;    }    // 部分匹配    public static int[] getNext(String s) {        // 定义数组        int next[] = new int[s.length()];        // 初始化i, j        int i = 0;        int j = -1;        next[0] = -1;        // 遍历        while (i < s.length() - 1) {            if (j == -1 || s.charAt(i) == s.charAt(j)) {                // 匹配成功                next[i] = j + 1;                i++;                j++;            } else {                //一旦不匹配成功j回退到-1                j = -1;            }        }        return next;    }    public static void main(String[] args) {        // 字符串1        String str1 = "BBCABCDAB ABCDABD";        // 字符串2        String str2 = "ABCDABD";        // 匹配表        int[] next = getNext(str2);        System.out.println(Arrays.toString(next));        // KMP算法        int result = Match(str1, str2, next);        System.out.println(result);    }}

输出结果:

[0, 0, 0, 0, 1, 2, 0]
10

到此，相信大家对"Java怎么实现KMP算法"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！