kmp算法_duncan算法

kmp 字符串匹配算法

1. s1为原字符串，长n，s2为目的字符串长度m，n>=m，想在s1中找到连续的n2
2. n*m级别的基本算法：从s1第i位开始，检查接下来的m位是否与s2相同，相同匹配成功，否则接着从i+1开始继续匹配m个字符。
3. kmp算法目的是，第i次匹配可以使用i-1次匹配失败的结果
   1. 假如当前s1匹配到c1处,s2匹配到c2处，尝试复用c2之前的匹配结果，s2的前c2个字符串是与s1往前c2长的字符串相同的；
   2. 假设s2的前c2位中，前j个字符与后j个字符相同（最长前缀与最长后缀匹配——最多前j个字符与后j个字符相同），那么就可以从s1的c1处接着匹配s2的j处；c2从0到m-1，需要保存对应的j，这就是next数组，目标字符串才有next数组
4. next数组求法，s位目标串
   1. next[0]为-1，标志着到了第0位（下面需要可以判断是否到了next的边缘），next[1]为0，表示当1处的字符不匹配，应该从0处开始重新匹配
   2. 从next[2]开始，使用next[0-i]的值计算next[i]：
      1. next[i]表示，s中第0到next[i]-1这next[i]位字符与i往前数next[i]位的字符匹配，
      2. 若i+1的值等于next[i]+1，则next[i+1]等于next[i]+1(第i+1位的最长前后缀为第i位加一)
      3. 否则查看next[next[i]]+1处字符是否与i+1处相同，这样next[i+1]为next[next[i]]+1
      4. 循环3，直到一直找到0处，这时next[i+1]为0

代码

public class KMP {
    public static void main(String[] a) {
        StringBuilder s1, s2;
        for(int i=0; i<1000; i++) {
            s1 = randomStr(3);
            s2 = randomStr(10);
            if((s2.indexOf(s1.toString()) != -1) && !match(s1.toString(), s2.toString())) {
                System.out.println("error");
                System.out.println("s1:" + s1);
                System.out.println("s2:" + s2);
                System.out.println();
                return;
            }
        }
        System.out.println("success");
    }

    public static StringBuilder randomStr(int n) {
        StringBuilder stringBuilder = new StringBuilder();
        for(int i=0; i<n; i++) {
            char c = (char)('a' + (int) (Math.random()*26));
            stringBuilder.append(c);
        }
        return stringBuilder;
    }

    public static int[] getNextArr(String s) {
        if(s == null || s.length() == 0) return new int[0];
        if(s.length() == 1) return new int[]{-1};
        if(s.length() == 2) return new int[]{-1, 0};
        int[] next = new int[s.length()];
        next[0] = -1;
        next[1] = 0;
        for(int i=2, j=0; i<s.length(); i++) {
            j = i-1;
            while(next[j]>-1 && s.charAt(i-1) != s.charAt(next[j])) {
                j = next[j];
            }
            next[i] = next[j] + 1;
        }
        return next;
    }

    public static boolean match(String s1, String s2) {
        int[] next = getNextArr(s1);
        for(int i=0, j=0; j<s2.length(); ) {

            if(s1.charAt(i) == s2.charAt(j)) {
                i++;
                j++;
                if(i == s1.length()) return true;
            } else {
                i = next[i];
                if(i == -1) {
                    i = 0;
                    j++;
                }
            }
        }
        return false;
    }
}
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
60
61
62

kmp jdk 实现

string的split方法
1

n^2级别的算法