1. kmp

在计算机科学中，字符串匹配是一个非常基础且高频的问题：给定一个主串 S 和一个模式串 P，我们需要在 S 中找到 P 出现的位置。

最直观的暴力匹配算法（Brute-Force）十分简单粗暴：用两个指针 i 和 j 分别指向 S 和 P，如果字符匹配，就齐头并进；一旦遇到不匹配的字符，主串指针 i 就要被迫“回退”到上一次开始匹配的下一个位置，而模式串指针 j 则回到起点重新开始。这种做法在最坏情况下的时间复杂度高达 $O(n \times m)$。

KMP算法（由 Knuth、Morris 和 Pratt 三人共同发明）的伟大之处就在于：它向我们证明了主串指针 i 是不需要回退的。

为什么可以不回退？因为在发生不匹配之前，前面那部分字符我们已经实打实地比较过了。KMP 算法的核心思想就是榨干这些“已知匹配信息”的全部价值。既然已经知道前面有哪些字符是匹配的，当在某个位置发生失配时，我们不让 j 回到起点，而是让它滑动到一个“最合理”的位置继续和当前的主串字符比较。

比如模式串 p=aabaad，主串 s=aabaabaad。当 p[5] 与 s[5] 失配时，我们确切知道前面成功匹配的子串是 aabaa。由于这部分子串存在内部重复的结构（p[0..1] == p[3..4]），我们只需将模式串向右滑动，直接用 p[2] 去和 s[5] 对齐并继续比较即可。这既保证了前面的字符依然完美贴合，又实现了步子迈得最稳的“最小回退”。

这就引出了一个关键问题：在任何位置失配时，如何决定模式串指针接下来该跳到哪里？

答案完全取决于模式串本身的结构。发生失配时，我们本质上是在寻找已匹配子串的“最大自我重叠”。我们试图将模式串向右滑动，寻找一个新下标，使得滑动距离最小且滑动后的模式串头部能和失配点前的主串已知字符匹配。

为了在匹配过程中能以 $O(1)$ 的时间瞬间查出跳跃位置，我们会提前对模式串进行预处理，把每个失配位置对应的“最小回退下标”记录下来，这就构成了 next 数组。

2. next 数组的推导与实现

next[i]: 当 p[i] 处失配时，模式串指针 i 应该回退到的下标（即滑动后用来与主串失配字符对齐的模式串新下标）。

很显然，如果p[0]失配，则必然要求p从s的下一个元素开始匹配。于是设next[0]=-1，表示p[0]应移动到s下一个下标再开始比较。

若p[1]失配，则尝试使用p[0]去匹配，next[1]=0

而在其他情况下，以模式串p=aabaad，求next[5]为例，可以这样计算：

1
2
3
4
5
s: aabaa | (失配)
p: aabaa | d <- i=5
    aaba | a <- i=4,但此时p[1]与p[2]不与s匹配
     aab | a <- i=3,但此时p[1]与p[2]不与s匹配
      aa | b <- i=2,此时匹配，最小回退，next[5]=2，完成.

若是p=abc，则next[2]=0。因为必须得回退到前面为空才行。空串与任何串匹配。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool compare(char s[], int len, int step){
	for(int i=0;i+step<len;++i){
		if(s[i]!=s[i+step]){
			return false;
		}
	}
	return true;
}

//如果模式串长度<2则退化到单个字符或空串，这种平凡情况不讨论。
int *next = (int *)malloc(sizeof(int)*pLen);
next[0] = -1;
next[1] = 0;
for(int i=2;i<pLen;++i){
    for(int j=1;j<=i;++j){
        if(compare(p,i,j)){
            next[i]=i-j;
            break;
        }
    }
}

使用即：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findSubStr(char * s, char * p, int * next, int sLen, int pLen){
    while (i < sLen && j < pLen) {
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == pLen) {
        return i - j;
    }
    return -1;
}

3. next数组的改进

但next数组仍会带来多余的比较：若next[i]==j且p[i]==p[j]时，当i处失配，说明主串在该处必然不是p[i]即p[j]，退到j必然还会再退回next[j]。那么p[j]与之比较就多余。

于是做一下改进，即在给next[i]赋值时加上：

1
2
3
if(p[i] = =p[next[i]]){
    next[i] = next[next[i]];
}