java的KMP算法

本文主要是介绍java的KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

KMP算法是由三个人共同提出，并以他们名字的首字母命名的，故叫做KMP算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
KMP算法要利用一个next数组：next[i]：从下标为0到i的子串的前缀和后缀相等的最大长度。同时也就表示要回退的位置（不是对称，是从左往右相等）

next求法

前缀：不包含最后一个字符的子串。比如aab的前缀是a或者aa
后缀：不包含第一个字符的子串。比如aab的后缀是b或者ab
求出next数组后，每次遇到不相等的字符，就去找它next数组中对应的前一个下标中的值，这个值就是要回退的位置（循环）
比如aaccaa所对应的next数组的值为0，1，0，0，1，2。

例子

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
输入：haystack = “hello”, needle = “ll”
输出：2
输入：haystack = “aaaaa”, needle = “bba”
输出：-1

    public int strStr(String haystack, String needle) {
        // haystack为匹配串，needle为模式串
        int n=needle.length();
        int m=haystack.length();
        if (n==0)
            return 0;
        // next[i]：表示要回溯的位置
        int[] next = new int[n];
        next[0]=0;
        // 求next数组（固定的方法）
        for (int i = 1,j=0; i < n; i++) {
            // 不相等
            while (j>0&&needle.charAt(j)!=needle.charAt(i)){
                j=next[j-1];
            }
            // 相等
            if (needle.charAt(j)==needle.charAt(i)){
                j++;
                next[i]=j;
            }
        }
        // 开始判断模式串的位置，如果j==模式串的长度就说明匹配成功了
        for (int i = 0,j=0; i < m; i++) {
            while (j>0&&haystack.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if (haystack.charAt(i)==needle.charAt(j))
                j++;
            if (j==n)
                return i-n+1;

        }

        return -1;
    }

这篇关于java的KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！