【Java】KMP算法(字符串匹配)

106 阅读 0 评论 70 点赞

我是靠谱客的博主畅快大地，最近开发中收集的这篇文章主要介绍【Java】KMP算法(字符串匹配)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

kmp算法

kmp算法是一种改进的字符串模式匹配算法，可以在O(n+m)的时间复杂度以内完成字符串的匹配操作。

利用得到的部分匹配，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到前面匹配过的位置，省去了大量的计算时间。

所以，kmp算法的核心就是计算next数组。next数组的主要实现方法有很多，就是要找到前后最长公共子序列的长度（即部分匹配值------”前缀”和”后缀”的最长的共有元素的长度）

KMP算法较朴素算法的优点：
1）在主串和子串匹配的过程中，主串不再回退，只改变子串的比较位置。
2）为子串生成对应的next数组，每次匹配失败，通过访问next数组获知子串再一次开始匹配的位置。

代码实现

kmp的核心思想就是主串的i不再后退，通过改变字串j的位置，继续和主串的字符串进行比较

 private static int kmp(String s, String t) {
        int i = 0;
        int j = 0;
        int[] next = getNext(t); // 分析字串
        System.out.println(Arrays.toString(next));
        while(i < s.length() && j<t.length()){
            //ABCER
            // CD
            if(j == -1 || s.charAt(i) == t.charAt(j)){
                i++;
                j++;
            } else {
                j = next[j]; //-1 j表示当前字符比较失败了
            }
        }

        if(j == t.length()){
            return i-j;
        } else {
            return -1;
        }
    }

获取字串t的kmp算法的next数组

private static int[] getNext(String t) {
        int[] next = new int[t.length()];
        int k=-1;
        int j=0;
        next[0] = -1;
        // 检测每一个字符之前的字符串，计算它们前后缀的最大长度，然后
        // 把长度记录在当前的next数组位置当中
        while(j < t.length()-1){
            if(k==-1 || t.charAt(k) == t.charAt(j))
            {
                ++j;
                ++k;
                // if主要处理ABCABC这种情况的优化
                if(t.charAt(k) == t.charAt(j)){
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
            }
            else
            {
                k = next[k]; // 前后缀长度需要缩减
            }
        }

        return next;
    }

在原始串s中，寻找子串t，如果找到，返回t在s串中首字母的下标值，字串没有找到，返回-1

private static int find(String s, String t) {
        int i = 0;
        int j = 0;
        while(i < s.length() && j<t.length()){ // O（n^2）
            if(s.charAt(i) == t.charAt(j)){
                i++;
                j++;
            } else {
                i = i-j+1;
                j = 0;
            }
        }

        if(j == t.length()){
            return i-j;
        } else {
            return -1;
        }
    }

测试代码

public static void main(String[] args) {
        String s = "000001000001";
        String t = "00001";
        String t1 = "AAAAAAA";
        int pos = kmp(s, t);
        System.out.println("pos:" + pos);
    }