KMP算法小结

KMP算法总结
    一般的字符串匹配，时间复杂度是O（m*n），KMP算法的时间复杂度为O（m+n）.
    一般的字符串匹配过程，一次匹配失败后，指针i（指向原串），指针j（指向子串）都回退至初始位置。而KMP核心思想是计算子串的next函数值（这个可以通过对子串进行预处理得到），据此决定指针i，j的指向。而子串的next函数值与原串无关，其实质是比较子串中末几位与首几位相同的位数情况。
    关于如何求得next函数值：
    （1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
    （2）next[j]= -1   意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1—k个字符与开头的1—k
个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。
如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
     （3）next[j]=k   意义：模式串T中下标为j的字符，如果j的前面k个
字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。
                       即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].（1≤k<j）;
      (4) next[j]=0   意义：除（1）（2）（3）的其他情况。

KMP算法Java实现代码

public class KMP {
    public static int[] next(char[] s)
    {
        int length = s.length;
        int next[]=new int[length];
        next[0]=-1;
        next[1]=0;
        for(int i=2;i<length;i++)
        {
            /*如果当前所求的数的前一位和他的next［］位相等的话，那么当前所求的位的next数就是它的前一位的next［］再加1*/
            int temp = next[i-1];
            while(temp!=-1&&s[i-1]!=s[temp])
            {
                temp = next[temp];
            }
            if(temp==-1) next[i] = 0;
            else next[i] = temp+1;
        }
        return next;
    }

    public static int compare(char[] t, char[] s)
    {
        int tlen = t.length;
        int slen = s.length;
        int [] next = next(s);
        int i,j;
        for(i=0,j=0;i<tlen-slen&&j<slen;)
        {
            if(t[i]==s[j]){
                i++;j++;
            }else{
                j=next[j];
                if(j==-1)
                {
                    i++;j++;
                }
            }
        }
        if(j<slen) return -1;
        else return i;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        char s[] = "abab".toCharArray();
        char t[] = "zhangabliababling".toCharArray();
        int temp = compare(t,s);
        System.out.println(temp);
       
    }

}