KMP算法

KMP解决的问题

字符串str1和字符串str2，str1是否包含str2，如果包含返回str2在str1中的位置。如何做到时间复杂度O(n)完成？

1
2
str1 111111112
str2 1112

这样如果使用暴力查找，复杂度较高，O(n*m) str1是n,str2是m

最长前缀和

求字符串中字符k前面的前缀和后缀的最大匹配个数。

例如字符串 abbabbk前后缀如下

1 2 3 4 5
前缀 a ab abb abba abbab
后缀 b bb abb babb bbabb
x x √ x x

对于k来说就前缀和后缀的最大匹配个数为3。

对于 aaaaak前后缀如下：

1 2 3 4
前缀 a aa aaa aaaa
后缀 a aa aaa aaaa
√ √ √ √

对于k来说就前缀和后缀的最大匹配个数为4。

KMP算法

KMP算法第一步就是求解字符串str每一位字符前面字符的前缀和后缀的最大匹配个数，叫nextarr，利用数组对查找进行加速。

对于字符串 aabaabsaa每一位的前缀和后缀的最大匹配个数如下（nextarr数组）：

a a b a a b s …
-1 0 1 0 1 2 3 …

对两个字符串str1,str2有如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
str1	i......X
str2	0......Y

经典算法
	当X不等于Y时
	对于暴力匹配算法str1会从X跳到第i+1位置，str2从Y跳到0位置开始匹配

对于KMP算法
	就会获得Y字符串之前的最大前缀最大，
	比对的X会停留，比对的Y位置回跳到最大前缀的结束位置.从这2个位置开始继续比对
	因为X之前的位置与Y位置之前的位置已经比较过，利用前缀和后缀做一个小加速
例如：
str1  ...abb[abbs]
str2     abbabbc

当比到s和c时发现2个字符串不相等，这时使用kmp算法 将str2直接从c调到第2个位置a,理解成以str1的的第4位a为开头能不能配成str2。

  1. 从可能不相等的位置开始往下走

  2. 证明从str1 第1位到第4位 中间任何一个位置配不成str2。

    1
    2
    3
    4
    5
    6
    7
    str1 i...k...j...X
    str2 0...........Y
    j是最大前缀的位置
    1.假设i到j 中存在k可以配出str2 
    2.那么k..x为str2前缀
    3.那么Y之前就找到了一个更大的前缀， k到x 这样就矛盾了。
    所以直接跳过到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
public class KMP {

    // 总复杂度O(N)
    public static int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }

        char[] str1 = s.toCharArray();
        char[] str2 = m.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int[] next = getNextArray(str2); //O(M)

        // O(N)
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) { // 字符相等，2个字符串同时往后移动
                i1++;
                i2++;
            } else if (next[i2] == -1) { // i2 == 0 str2比对的位置不能再往前了，已经是0位置了，让str1换个开头继续推 str1[i + 1]
                i1++;
            } else { // str2可以往前跳 调到最大前缀的位置进行比对
                i2 = next[i2];
            }
        }

        // 如果str2匹配完成，找到该位置。 否则返回 -1
        return i2 == str2.length ? i1 - i2 : -1;
    }

    private static int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1; //默认为-1
        next[1] = 0;
        int i = 2; // next数组开始的位置
        int len = 0; //表示最长的公共子串长度
        while (i < ms.length) {
            if (ms[i - 1] == ms[len]) { //如果相等 abbe[len] abbe[i]
                next[i++] = ++len; //这一位的next数组就等于 上一位的最大前缀 + 1
            } else if (len > 0) { // abbe abbc
                len = next[len]; // 如果不相等找len位置的最大前缀进行比较
            } else {
                next[i++] = 0; //这一位没有最大前缀
            }
        }
        return next;
    }

    public static void main(String[] args) {
        System.out.println(getIndexOf("babcabcd", "abcabcd"));
    }
}