KMP算法

KMP暴力方法为何暴力？

因为每个位置的尝试对后面位置的尝试都没有任何帮助，每个位置的尝试是独立的！

了解KMP之前，先认识一种信息：前缀与后缀串的最长匹配长度

K之前的字符串中，前缀跟后缀的最长相等长度，而且限定，前缀串不能取到整体，后缀串也不能取到整体。

package com.harrison.class16;

/**
 * @author Harrison
 * @create 2022-03-29-9:24
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */
public class Code01_KMP {
    public static int getIndexOf(String s1,String s2){
        if(s1==null || s2==null || s2.length()<1 || s1.length()<s2.length()){
            return -1;
        }
        char[] str1=s1.toCharArray();
        char[] str2=s2.toCharArray();
        int x=0;
        int y=0;
        int[] next=getNextArray(str2);
        while(x<s1.length() && y<s2.length()){
            if(str1[x]==str2[y]){
                x++;
                y++;
            }else if(next[y]==-1){// y==0
                x++;
            }else{
                y=next[y];
            }
        }
        // y越界代表 str1的某个开头已经匹配出了str2
        return y==s2.length()?x-y:-1;
    }

    /*
    next[]数组记录：
    1.最长前缀和最长后缀的长度
    2.前缀中下一个字符在哪
     */
    public static int[] getNextArray(char[] str2){
        if(str2.length==1){
            return new int[]{-1};
        }
        int[] next=new int[str2.length];
        next[0]=-1;
        next[1]=0;
        // 目前在哪个位置上求next数组的值
        int i=2;
        // 前缀的下一个字符都跟当前位置的前一个字符比较
        // 当前是哪个位置的值在和i-1位置的字符比较
        int cn=0;
        while(i<next.length){
            if(str2[i-1]==str2[cn]){// 配成功的时候
                next[i++]=++cn;
            }else if(cn>0){
                cn=next[cn];
            }else{
                next[i++]=0;
            }
        }
        return next;
    }

    public static String getRandomString(int possibilities,int size){
        char[] ans=new char[(int)(Math.random()*size)+1];
        for(int i=0; i<ans.length; i++){
            ans[i]=(char)((int)(Math.random()*possibilities)+'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int matchSize = 5;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            String match = getRandomString(possibilities, matchSize);
            if (getIndexOf(str, match) != str.indexOf(match)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }
}