KMP 是一种字符串的模式匹配算法，可以在最多只遍历一遍主串的情况下，实现两个字符串的匹配。时间复杂度 O(m+n)

字符串匹配问题

子串的定位操作通常称为串的模式匹配，他求的是字串（通常成为模式串）在主串中的位置。
很容易想到一种朴素的暴力解法。
直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Index(string S,string T)
{
    int i=0,j=0;
    while(i<S.length() && j < T.length())
    {
        if(S[i] == T[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }

    if(j == T.length())
    {
        return i - T.length();
    }
    return -1;
}

在上述算法中，分别用计数指针 i，j 指示主串 S 和模式串 T 中当前正在比较字符的位置。从主串 S 的第一个字符开始，与模式串的第一个字符进行比较，若相等，则继续逐个比较后序的字符，否则从主串的下一个字符起，重新和模式串的字符进行比较，以此类推，直到模式串 T 中的每个字符依次和主串中的一个连续的字符序列相等，则匹配成功。否则匹配不成功。
这种暴力尝试的最坏时间复杂度是 O(n*m)其中 n 和 m 是主串和模式串的长度。
演示动画如下

KMP 算法

在上述动画演示中，第三趟匹配中 i=6，j=4 的字符比较不想等，于是又从 i=3，j=0 重新开始比较，然而仔细观察一下就会发现，i=3，j=0、i=4，j=0、i=5，j=0 这三次比较都是不必进行的，因为在第三趟的部分匹配结果上我们就已经知道了主串的第 3、4、5 的字符是 b、c、a。而模式串的第一个字符是 a 我们也是知道的，所以 3、4 两个位置可以直接跳过，因为一定不符合，而 5 的位置不需要比较，因为一定符合，所以可以直接进心 i=6、j=1 的比较。

我们利用一下这个思想改良一下上述算法。动画演示如下

用代码实现一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Index(string S,string T,int next[])
{
    int i=0,j=0;
    while(i<S.length() && j < (int)T.length())
    {
        if(j == -1 || S[i] == T[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }

    if(j == T.length())
    {
        return i - T.length();
    }
    return -1;
}

这段代码和上面的代码的主要有两处改动，第一处是 13 行，匹配失败的时候不回溯而是查表，j 跳转到下一个应该匹配的位置。第二处是第 6 行的判断加上了j == -1的判断，这相当于一个 flag，代表第一个就匹配失败的意思，下面求 next 数组的过程会提到。

next 数组计算

在上述算法实现中直接使用了一个 next 数组来表示匹配失败之后 j 应该从哪个位置重新匹配。那么这个 next 数组如何计算呢。
以上述模式串 Tabcac为例：
next[0]一定是-1，这个-1 只是一个 flag 位，只要去不到真正数组中的位置即可，这个标记位代表的意思是第一个就匹配失败，主串指针需要右移。
next[1]一定是 0，模式串的第 1 个匹配失败，主串需要和模式串的第 0 个进行重新匹配。
next[2] = next[3] = 0 没有可以省略的匹配
next[4] = 1，因为如果在 j = 4 的位置匹配失败，那么 j = 3 时匹配成功的，那么 i -1 的位置一定是 a 所以可以省略掉第 0 个位置的判断。

编号 0 1 2 3 4
T a b c a c
next -1 0 0 0 1
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void get_next(string T,int next[])
{
	next[0] = -1;
	int i = 0,j = -1;
	while(i < T.length())
	{
		if(j == -1 || T[i] == T[j])
		{
			++i;++j;
			next[i] = j;
		}else
		{
			j = next[j];
		}
	}
}

KMP 算法进一步优化

假如模式串 T = “aaaab”那么 next 数组如下

编号 0 1 2 3 4
T a a a a b
next -1 0 1 2 3

假如在 j = 3 的时候匹配失败，j = 2 而此时 T[2] = T[3] 所以在 2 这里肯定也会失败。j 跳转到 i,而此时 T[1] = T[2]所以 1 这里也会失败。这些比较都是没有意义的，因此可以对 next 数组进行进一步的优化成如下

编号 0 1 2 3 4
T a a a a b
next -1 -1 -1 -1 3

代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void get_next(string T,int next[])
{
	next[0] = -1;
	int i = 0,j = -1;
	while(i < T.length())
	{
		if(j == -1 || T[i] == T[j])
		{
			++i;++j;
			next[i] = j;
		}else
		{
			j = next[j];
		}
	}
}