Java KMP算法代码

1. KMP 算法(字符串匹配算法)较 BF(朴素的字符串匹配)算法有哪些改进

1）在主串和子串匹配的过程中，主串不再回退，只改变子串的比较位置。

2）为子串生成对应的next数组，每次匹配失败，通过访问next数组获知子串再一次开始匹配的位置。

2. 在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的

前缀。

因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。

public class KMP {

    public static void main(String[] args) {

        String a="aawsadabbb";

        String b="abb";

        System.out.println(KMP(a,b));

    }

    public static int  KMP(String s,String t ){

        int i=0;

        int j=0;

        int []next=getNext(t);

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

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

                i++;j++;

            }else {

                j=next[j];

            }

        }

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

            return i-j;

        }else {

            return -1;

        }

    }

// 求取next数组

    private static int[] getNext(String t) {

        int k=-1;

        int j=0;

        int []next=new int[t.length()];

        next[0]=-1;

        while (j<t.length()-1){

            if(k==-1||t.charAt(k)==t.charAt(j)) {

                k++;

                j++;

                next[j]=k;

            }else {

                k=next[k];

            }

        }

        return next;

    }

}

巴特西

Java KMP算法代码

最新文章

热门文章