kmp算法(java)_java kmp算法

前言

开始是跟着大话数据结构敲的,结果是数组越界
后来找了骗其它博主的文章,推了下他的思路,发现他的结果是正确的,next数组的值是不对的(跟暴力匹配没啥区别),又找了找其它的文章,竟然发现不止一位是按这种思路写的…

思路

思路可以看看他的
代码可以参考我的,思路清晰,注释详细

代码

package myPackage;

public class KMP {

    public static int[] getNext(char[] str) {
        int[] next = new int[str.length];
        next[0] = -1;
        next[1] = 0;
        int j;
        for (int i = 2, len = str.length; i < len; i++) {
            j = next[i - 1];
            while (j != -1) {
                if (str[i - 1] == str[j]) {
                    next[i] = j + 1;
                    break;
                } else {   //如果不相等
                    j = next[j];    //向上折,知道遇到第0个下标的-1
                }
                next[i] = 0;    //防止没有匹配,如果没有匹配则从第一个字符重新开始匹配
            }
        }
        return next;
    }

    public static int kmpMatch(char[] mainStr, char[] subStr) {
        int[] next = getNext(subStr);    //获取next数组
        int i = 0, j = 0;
        while (i < mainStr.length && j < subStr.length) {
            if (j == -1 || mainStr[i] == subStr[j]) {     //subStr处于第一个元素或者mainStr[i]与subStr[j]的元素相同
                i++;
                j++;
            } else {
                j = next[j];      //相当于subStr数组向后移动
            }
        }

        if (j == subStr.length)    //j会比实际值大一,相等说明匹配成功
            return i - j;

        return -1;   //匹配不成功,返回-1
    }

    public static void main(String[] args) {
        int status = kmpMatch("JSABCDABCDLDFJ".toCharArray(), "BCDABCD".toCharArray());
        if (status == -1) {
            System.out.println("匹配失败");
        }
        System.out.println("匹配成功,起始下标为:" + status);
    }

}
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

效果