算法-KMP匹配

下面是原码

BF暴力匹配

 public static int BF(String str1,String str2){
        /**
         * 这个其实就是我们的暴力匹配的算法,就是进行同步增加匹配,如果匹配不成功就把 j == 0; i == i - j + 1;
         */
 
        //这个其实我们这样写的好处还有一个就是以后不用在进行函数的调用消耗我们的内存
        int m = str1.length();
        int n = str2.length();
 
        int i = 0;//这个是我们主串的遍历位置
        int j = 0;//这个是我们字串的遍历位置
 
        while(i < m && j < n){
            if(str1.charAt(i) == str2.charAt(j)){
                i++;
                j++;
            }else{
                i = i - j + 1;//这里为什么置为这个数值是因为我们的i 跟 j 是同步变化的(下次便利的时候更换起点为这个值)
                j = 0;
            }
        }
        if(j == n){
            return i - j;
        }
        return -1;
    }

KMP算法

public static int[] getNext(String s,int strlen){
        int[] next = new int[strlen];
        if(strlen == 1){
            return new int[]{-1};
        }
        next[0] = -1;
        next[1] = 0;
        int cn = 0;// cn 就是我们的需要next数组的下标值前一个要比较的下标
        int i = 2;// i 就是我们需要的next数组的值的下标,(起始位置就是我们的2)
        while(i < strlen){
            if(s.charAt(i-1)==s.charAt(cn)){
                next[i++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else{
                next[i++] = 0;
            }
        }
        return next;
    }
 
    public static int KMP(String str1,String str2){
        int m = str1.length();
        int n = str2.length();
        int[] next = getNext(str2,n);
        int i = 0;
        int j = 0;
        while(i < m && j < n){
            if(str1.charAt(i) == str2.charAt(j)){
                i++;
                j++;
            }else if(j == 0){
                i++;
            }else{
                j = next[j];
            }
        }
        return j == m ? i - j : -1;
    }

暴力求解我们next数组

public static int[] conNextArray(String str){
        int[] arr = new int[str.length()];
        arr[0] = -1;
        arr[1] = 0;
        for(int i = 2; i < str.length(); ++i){
            int count = 0;
            int flag = 0;
            for(int j = i - 1; j > 0; --j){
                if(str.substring(0,j).equals(str.substring(i - j, i))){
                    if(flag != 1){
                        arr[i] = j;
                        flag = 1;
                        break;
                    }
                }
            }
        }
        return arr;
    }