KMP字符串匹配算法

publicclassKMP {

    staticint[] next;    /**

     *

     * @param t  模式串，求得模式串回溯的next函数

     */

    staticvoidnext(String t) {

        next = newint[t.length()];

        next[0] = -1;

        intj = -1;

        inti = 0;

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

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

                i++;

                j++;

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

                    next = next[j];

                }else{

                    next = j;

                }

            }else{

                j = next[j];

            }

        }    }

    /**     *

     * @param s 主串

     * @param t 模式串

     * @param pos 从主串的pos下标位置开始匹配

     */

    staticintmatch(String s,String t,intpos){

        inti=pos;

        intj=0;

        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()-1){

            returni-j;

        }else{

            return-1;

        }    }

    publicstaticvoidmain(String[] args) {

        String s = "aaaasad";

        String t = "sa";

        next(t);

        System.out.println(match(s,t,0));

    }}