KPM算法思想及实现_完整的kpm算法程序

一、比较暴力算法和KMP算法

1、暴力算法：

双指针遍历主串和子串，当发现主串和子串不匹配时，双指针同时回溯

2、KMP算法：

双指针遍历主串和子串，当发现主串和子串不匹配时，通过比较子串的next数组只回溯子串指针，从而提高算法速度

二、next数组含义

next[j]=第j位字符前面的j-1位字符所组成的子串的最长公共前后缀长度

三、计算next数组

计算子串每个字符左子串的最长公共前后缀长度

四、算法实现

public class KMP {
    public static void main(String[] args) {
        String str="abcksljafkdshfjksd";
        String subs="sl";
        System.out.println(kmp(str,subs));

    }

    /**
     * 遍历比较字符串
     * @param str 主串
     * @param subs 子串
     * @return 子串在主串出现的第一个位置下标
     */
    public static  int  kmp(String str,String subs){
        char[] subc=subs.toCharArray();                 //将子串转换成字符数组方便计算next数组
        int[] next=new int[subc.length];                //声明next数组
        getNext(subc,next);                             //计算next数组
        int i=0,j=0;                                    //双指针遍历主串和子串
        while(i<str.length()&&j<subs.length()){
            if(j==-1||str.charAt(i)==subs.charAt(j)){
                i++;j++;
            }
            else{
                j=next[j];                              //子串回溯
            }
            if(j==subs.length()){
                return i-j;                             //返回index下标
            }
        }
        return -1;
    }
    /**
     * 计算改变next数组（计算最长公共前后缀的值）
     * @param subc 子串
     * @param next next数组
     */
    public static void getNext(char[] subc,int[] next){
        next[0]=-1;                                 //设置数组第一位为-1
        if(subc[1]==subc[0]){                      //判断子串第二位与第一位是否相等
            next[1]=1;                              //相等赋值为1，表明此时最长公共前缀为1
        }else{
            next[1]=0;                              //反之赋值为0
        }
        int i=2;                                    //从子串下标为2的位置开始计算
        int j=-1;                                   //此时j为next[0]的值
        while(i<subc.length){                       //遍历子串
            if(j==-1||subc[i-1]==subc[j]){          //判断上一个最长公共前后缀后的字符是否相等
                next[i++]=++j;                      //最长公共前后缀长度加一
            }
            else{
                j=next[j];                          //往前递归找上一个最长公共前后缀
            }
        }
    }


}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59