算法-KMP

KMP算法的作用在于在一个主串中查找一个主串。

传统查找子串的方法是一个字符一个字符的比较，代码如下：

 public static int notKMP(String main,String sub){

        for (int i=;i<main.length();i++){

            int j=;

            int k=i;

            while (main.charAt(k)==sub.charAt(j)){

                k++;

                j++;

                if (j==sub.length()){

                    return i;

                }

            }

        }

        return -;

    }

这种方式在遇到不相同的时候，主串往下移动一位，子串恢复到0.继续的进行对比。

KMP的算法的有点在于子串中如果有相同的部分的话，那么可以省略一部分的校验，下面这个图加深一些印象：

如果我们使用KMP算法的话，那么中间的红框的那部分是不需要比较的，很显而易见，因为他们都第一步进行了比较了，当然怎么判断还是需要算法的。

算法的步骤分为两部分，第一部分是算出子串的next数组，这个数组表达的就是子串的相似度，具体算法实现：

 /**

     * 返回KMP数组

     * @param str

     * @return

     */

    public static int[] getNextArr(String str){

        int[] nexts=new int[str.length()];

        //j=1 的时候为0  j=2的时候为1

        nexts[]=;

        nexts[]=;

        for (int j=;j<str.length();j++){

            int index=;

            for (int i=;i<j-;i++){

                if(str.substring(,i+).equals(str.substring(j-i-,j))){

                    index++;

                }

            }

            nexts[j]=index;

        }

        return nexts;

    }

第二部分就是进行匹配：

 /**

     *

     * @param s 主串

     * @param t 子串

     * @param pos 从主串哪个位置开始匹配

     * @return

     */

    public static int indexKMP(String s,String t,int pos){

        int i=pos;

        int j=;

        int[] nexts=getNextArr(t);

        while (i<s.length()&&j<t.length()){

            if (j==||s.charAt(i)==t.charAt(j)){

                i++;

                j++;

            }else {

                j=nexts[j-];

            }

        }

        if (j>=t.length()){

           return i-t.length();

        }

        return ;

    }

. 总的来讲就是只关注子串，出现相同的那部分可以不进行比较。

巴特西

算法-KMP

最新文章

热门文章