Java教程

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算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!