KMP算法

KMP算法是字符串相关的一个经典算法，主要用于解决这样一个问题：

有一个长度为m文本串S，和一个长度为n模式串P（m > n > 0），如何高效查找P在S中的位置

首先我们想到的方法有暴力匹配法，显然，这个方法是十分低效的，最坏情况下复杂度为O(m*n)，有没有一个O(m+n)的算法呢？这个算法就是今天的主题

暴力匹配法

首先，我们看一下暴力匹配法，直接比较即可，不作展开

public int violentSearch(String s, String p) {
    // ...略去条件检查
    for (int i=0, end=s.length()-p.length()+1; i!=end; i++) {
        if (match(s, i, p)) {
            return i;
        }
    }
    return -1;
}

private boolean match(String s, int pos, String p) {
    for (int i=0, end=p.length(); i!=end; i++) {
        if (s.charAt(pos+i) != p.charAt(i)) {
            return false;
        }
    }
    return true;
}

KMP算法

我们先看一下KMP是怎么做的
KMP算法充分利用了字符串匹配的先验信息，没有必要每次都重新比较整个字符串

举个例子

假设有如下s：abcdbabcda, p: abcda

0	1	2	3	4	5	6	7	8	9
a	b	c	d	b	a	b	c	d	a
a	b	c	d	a

当我们开始比较时，暴力匹配法的策略是继续往后挪动1位，从1处开始执行

	0	1	2	3	4	5	6	7	8	9
	a	b	c	d	b	a	b	c	d	a
	a	b	c	d	a
1		a	b	c	d	a
2			a	b	c	d	a
3				a	b	c	d	a
4					a	b	c	d	a

此时，而KMP会从第4位开始比较，也就是

0	1	2	3	4	5	6	7	8	9
a	b	c	d	b	a	b	c	d	a
				a	b	c	d	a

从第4位开始，意味着往后挪动4位，为什么是4位呢？

最长匹配前缀表

让我们忘记往后挪动4位这件事
先看一下abcd，将字符串往后挪动1位/2位/3位

	0	1	2	3
	a	b	c	d
挪动1位		a	b	c
挪动2位			a	b
挪动3位				a

显然，都显然不等，可以直接跳过这部分无用的比较
如果我们知道了上面这个规律，就可以大大减少比较次数，KMP算法便是利用这个规律
上述这个规律，在KMP算法中，抽象为构造最长匹配前缀表

构造最长匹配前缀表

比较可能在字符串前缀的任意一处发生不匹配，我们需要生成所有子串的匹配表
以abcda为例，我们的思路是寻找所有子串的最长匹配

		0	1	2	3	4
		a	b	c	d	a
0	0	a
1	0	a	b
2	0	a	b	c
3	0	a	b	c	d
4	1	a	b	c	d	a

如何用程序来生成呢？
换个有代表性的例子aabaaa
最长前缀匹配长度记为prefix

		0	1	2	3	4	5	6
index	prefix	a	a	b	a	a	a	a
0	0	a
1	1	a	a
2	0	a	a	b
3	1	a	a	b	a
4	2	a	a	b	a	a
5	2	a	a	b	a	a	a
6	2	a	a	b	a	a	a	a

简化一下表格

	-1	0	1	2	3	4	5	6
		a	a	b	a	a	a	a
prefix		0	1	0	1	2	2	2
模拟位置			k		i

定义：
下标 i 表示当前匹配表需要生成的位置
下标 k 表示当前匹配的最长前缀位置[-1, k)

从-1开始计数，能准确说明问题。

显然，[-1,k) 与 [i-k, i)是相等的
当i=3 ，此时，k=1

	-1	0	1	2	3	4	5	6
		a	a	b	a	a	a	a
prefix	-1	0	1	0	1	?	?	?
模拟位置			k			i

当 i=4时，k=1
分析一下
[-1,k) 与 [i-k, i)是相等的
比较 k 与 i 的值，此时相等，从而，prefix[i] = ++k，即2

	-1	0	1	2	3	4	5	6
		a	a	b	a	a	a	a
prefix		0	1	0	1	2	?	?
				k			i

继续分析i=5, k=2
[-1,k) 与 [i-k, i)是匹配的
比较 k 与 i 的值，不相等，需要重新计算prefix[i]

如何重新计算prefix[i]呢？
根据前面的条件，[-1,k) 与 [i-k, i)匹配，也就是s[-1, k]==s[i-k, i]
s[-1, k]的最长前缀，与s[i-k, i]中的最长前缀等价
从而，s[-1, k]段中的最长前缀s[-1, ?]，在s[i-k, i]中也必然存在对应的s[i-k, ?]
根据最长前缀匹配的定义，此时，i 位置的最长匹配取决于此时的 ? 位置与 i 位置的值是否相等，如果相等，prefix[i]为?的位置，否则继续向前查找s[-1, ?]中的相对最长前缀
上面这个过程是计算prefix表的核心过程

代码实现

根据上述过程，我们不难写出初步的代码

int[] kmpPrefix(String pattern) {
    // ...略去条件检查
    int len = pattern.length();
    int[] prefix = new int[len];
    int k = 0;
    for (int i=1; i!=len; i++) {
        if (pattern.charAt(k) == pattern.charAt(i)) {
            prefix[i] = k;
            k ++;
        } else {
            // 不相等，需要迭代查找，直到不存在
            do {
                k = prefix[k - 1];  // 定位下一可能的最长匹配位置
            } while (pattern.charAt(k) != pattern.charAt(i) && k>0);
            if (pattern.charAt(k) == pattern.charAt(i)) {
                prefix[i] = k;
                k ++;
            } else {
                prefix[i] = k;
            }
        }
    }
    return prefix;
}

优化一下这段代码，将后半部分的条件检查放到前面

int[] kmpPrefix(String pattern) {
    // ...略去条件检查
    int len = pattern.length();
    int[] prefix = new int[len];
    int k = 0;
    for (int i=1; i!=len; i++) {
        // 不相等，需要迭代查找，直到不存在
        while (pattern.charAt(k) != pattern.charAt(i) && k>0) {
            k = prefix[k - 1];  // 定位下一可能的最长匹配位置
        }
        if (pattern.charAt(k) == pattern.charAt(i)) {
            k ++;
        }
        prefix[i] = k;
    }
    return prefix;
}

主过程

构造完最长前缀匹配表之后，剩下的过程就是根据匹配表，完成字符串匹配

举个例子

我们看下面的例子
s：ababbababa, p: ababa

	0	1	2	3	4
	a	b	a	b	a
prefix	0	0	1	2	3

i	i	i	i	i	i
0	1	2	3	4	5	6	7	8	9
a	b	a	b	b	a	b	a	b	a
a	b	a	b	a
j	j	j	j	j
y	y	y	y	n
		a	b	a	b	a
				j
				a	b	a	b	a
				j
					a	b	a	b	a
					j

根据prefix，最长匹配前缀为2，于是，我们将比较的位置从p串的第2位开始重新匹配，s串比较的位置从不匹配处开始即可，表中演示了两次匹配的过程

代码实现

public int kmp(String s, String p) {
    // ...略去条件检查
    int[] prefix = kmpPrefix(p);
    for (int i=0, j=0, end=s.length(); i!=end; i++) {
        while (j>0 && s.charAt(i) != p.charAt(j)) {
            j = prefix[j-1];
        }
        if (s.charAt(i) == p.charAt(j)) {
            j ++;
        }
        if (j == p.length()) {
            return i - j + 1;
        }
    }
    return -1;
}

至此，KMP算法结束