暴力匹配

public class ViolenceMatch {
    public static void main(String[] args) {
        String str1="黑马程序员硅谷尚硅谷你好";
        String str2="尚硅谷";
        int index=violenceMatch(str1,str2);
        System.out.println("index="+index);
    }
    public static int violenceMatch(String str1,String str2)
    {
        char[]a= str1.toCharArray();
        char[]b=str2.toCharArray();
        int i=0;int j=0;
        while(i<a.length&&j<b.length)
        {
            if(a[i]==b[j])
            {
                ++i;++j;
            }
            else {
                i=i-j+1;j=0;
            }
        }
        if(j==b.length)
        {
            return i-j+1;
        }
        else {
            return -1;
        }
    }
}

最坏时间复杂度O(nm)，n是主串的长度，m是模式串的长度

KMP算法

移动位数=已匹配的字符数-对应的部分匹配值
时间复杂度O(n+m)
对算法的改进
将PM表的next数组右移一位，就可以直接查看部分匹配值。第一个元素用-1填充。Move=(j-1)-next[j]
子串比较指针右移：j=j-Move=j-((j-1)-next[j])=next[j]+1
这PM表的next数组整体加一。
next[j]数组的含义：在子串的第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较。

next数组值推导
如果前后缀一个字符相等，k值是2，两个字符k值是3，n个相等k值是n+1

这段代码是为了计算出子串的next数组

public static int[] kmpNext(String patternString)
    {
        //创建一个next数组保存部分匹配值
        int[]next=new int[patternString.length()];
        //如果字符串的长度为1，则部分匹配值就是0
        next[0]=0;
        for(int i=1,j=0;i<patternString.length();i++)
        {
            //当patternString.charAt(i)!=patternString.charAt(j)，我们需要从next[j-1]获取新的j
            //直到我们发现有patternString.charAt(i)==patternString.charAt(j)成立才退出。这是KMP算法的核心
            while(j>0&&patternString.charAt(i)!=patternString.charAt(j))
            {
                j=next[j-1];
            }
            //当patternString.charAt(i)==patternString.charAt(j)成立时，部分匹配值+1
            if(patternString.charAt(i)==patternString.charAt(j))
            {
                j++;
            }
            next[i]=j;
        }
        return next;
    }