KMP及扩展KMP
KMP之所以在竞赛中常见，并不是因为它用来匹配字符串，而是用它的next数组，为了介绍它，我们先讲讲最长公共前缀
最长公共前缀
我们拿字符串ababcab作为例子
| string | a | b | a | b | c | a | b |
|---|---|---|---|---|---|---|---|
| len | 0 | 0 | 1 | 2 | 0 | 1 | 2 |
这里所表达的是，例如取第3、4个字符”ab”，这个子串与前缀完全匹配，且它的长度是2，所以就记录2，而第3、4、5个字符”abc”与前缀不能完全匹配，就记作0，含义就这么简单，而且你会发现，计算b的时候，可以根据它所匹配的字符的偏移来，b如果是匹配的，就找到匹配的那个字符是数组中的第几个，它是第二个，所以填2进去。我们再来看更复杂的例子
| string | a | b | a | c | a | b | a | b |
|---|---|---|---|---|---|---|---|---|
| len | 0 | 0 | 1 | 0 | 1 | 2 | 3 | 2 |
最后那个字符不匹配的时候，1是怎么计算出来的呢，直接重新计算当然也可以，但就出现重复计算了。我们考虑一下匹配过程，在前面的字符a的时候，前后各一个指针，像这样
| string | a | b | a | c | a | b | a | b |
|---|---|---|---|---|---|---|---|---|
| len | 0 | 0 | 1 | 0 | 1 | 2 | 3 | ? |
| pointer | ^ | ^ |
然后两个a匹配，arr[6] = pointer1 - arr 得到3，然后两指针一起移动
| string | a | b | a | c | a | b | a | b |
|---|---|---|---|---|---|---|---|---|
| len | 0 | 0 | 1 | 0 | 1 | 2 | 3 | ? |
| pointer | * | ^ | ^ |
这时候，不匹配，那么前一个指针上一次指向的是arr[2]的位置，即图上*的地方，值是1，这个值如果是p，那就移动到arr[p]的地方，所以就移动到arr[1]的地方，本质上就是找到前一个匹配此后缀的位置，即
| string | a | b | a | c | a | b | a | b |
|---|---|---|---|---|---|---|---|---|
| len | 0 | 0 | 1 | 0 | 1 | 2 | 3 | 2 |
| pointer | ^ | ^ |
然后再尝试匹配，这次匹配上了，然后前一指针指向第二个元素，所以赋值2
next数组
以上过程你需要细细理解，在理解以上过程后，再去理解next数组就非常简单了，next数组只是把以上数组加了一偏移，如下
| string | a | b | a | c | a | b | a | b | \0 |
|---|---|---|---|---|---|---|---|---|---|
| next | -1 | 0 | 0 | 1 | 0 | 1 | 2 | 3 | 2 |
这么做是为了简化代码的书写，当然你直接用公共前缀的那个数组来做也是可以的
不过本文不介绍怎么做字符串匹配，这种文章到处都是，我们要讲的是竞赛中的典型应用
生成next数组的算法的时间复杂度为 $O(n)$ ，n是数组长度
应用1 poj2406
题目大意是给你一个字符串s，找出一个串a，使得a自己重复n次，便得到字符串s，要找到最大的n值。例如ababab，可以找到ab重复3次得到，所以输出3。像这种就是next数组表演的时候，它在计算自匹配方面非常合适，我们先再来理解一下next数组，它的值表示与前缀的重复长度，那么看下表，使用长度为102的abab....abab
| string | a | b | a | b | … | b | a | b | \0 |
|---|---|---|---|---|---|---|---|---|---|
| next | -1 | 0 | 0 | 1 | … | 97 | 98 | 99 | 100 |
我们发现，使用串长102减去next数组最后一个值，自然就得到了重复前缀的最短长度，既然它是最短的，那么我们用总长102除以2，就得到了重复的次数，就是我们想要的答案。当然前提是能整除，如果不能整除那么这样的前缀便不存在，输出1就行了。
应用2 poj2752
题目大意是给你一个字符串s，找出所有前缀等于后缀的串长。我们先来试试算一个短点的ababcababcabab
| string | a | b | a | b | c | a | b | a | b | c | a | b | a | b | \0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| next | -1 | 0 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
可以轻松看出next的最后一个值9肯定就是其中一个长度，那接着呢？我们需要回想一下，构造这个数组的时候，如果匹配失败，是怎么找到前一个匹配当前后缀的前缀的，这个值如果是p，那就移动到arr[p]的地方，如果你还记得这个，那就好办了，我们取arr[9]，结果是4，再取arr[4]结果是2，再取arr[2]，结果是0，循环结束，所以加上整个串长14就是我们所要的答案了，完整结果是2 4 9 14。
应用3 子串出现次数
给你主串s和子串t，求t在s中出现了多少次，例如s="abababa"，t="aba"，那么t在s中出现了3次。
这里运用到一个技巧，我们把s和t连接成这个串u="aba#abababa"，即把t放在s的前面并中间使用#分隔，这个符号在两个串中都没有出现。然后我们对u计算next数组，那么next数组中值等于t的长度的元素个数就是答案。
应用4 可重叠最长重复子串
大意是给你一个字符串s，任意选取两个不同的起始位置i和j，这两个位置的后缀串有相同的前缀，这个前缀可以重叠，问这个相同的前缀的最大长度
例如eabcaefabcabc，最长重复子串是abca，长度是4。
KMP在生成的时候，总是以串的前缀作为匹配对象，我们要做的，就是遍历那个字符串的每一个后缀，都生成一次next数组，而在生成过程中出现的最大值就是答案，所以时间复杂度 $O(n^2)$ 。当然我们还有更好的算法，这个之后再讲。
Z Algorithm
Z函数的定义是对于字符串s，生成数组z，定义z[i]是s.substr(i)与s的最长相同前缀长度
样例如下
| string | a | b | a | c | a | b | a | c | \0 |
|---|---|---|---|---|---|---|---|---|---|
| Z | 8 | 0 | 1 | 0 | 4 | 0 | 1 | 0 | 0 |
扩展KMP需要依赖这个z数组，但是在介绍这个之前，我们先介绍下面的扩展KMP
扩展KMP
所谓扩展KMP，即给定两个字符串s和p，需要求出数组ext，其中ext[i]的值表示s.substr(i)与p的最长相同前缀长度
这个算法依赖 Z Algorithm 中生成的z数组。
为了比较容易理解，我省略一堆说明，我们直接来模拟匹配过程，一边模拟一边解说，一开始数据如下，i是匹配位置指针
| string | b | a | a | b | a | c | a | c | \0 |
|---|---|---|---|---|---|---|---|---|---|
| i | ^ | ||||||||
| p | a | b | a | c | a | b | |||
| Z | 6 | 0 | 1 | 0 | 2 | 0 | |||
| ext | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | - |
上表，一开始，不匹配，不操作，移动p
| string | b | a | a | b | a | c | a | c | \0 |
|---|---|---|---|---|---|---|---|---|---|
| e | ^ | ||||||||
| i | ^ | ||||||||
| p | a | b | a | c | a | b | |||
| Z | 6 | 0 | 1 | 0 | 2 | 0 | |||
| ext | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | - |
这时，p与s[i]是匹配的，我们用e指针记录未能匹配的位置，并写入ext[i]=e-i得1
继续移动p，并更新e，得到下表
| string | b | a | a | b | a | c | a | c | \0 |
|---|---|---|---|---|---|---|---|---|---|
| e | ^ | ||||||||
| i | ^ | ||||||||
| p | a | b | a | c | a | b | |||
| Z | 6 | 0 | 1 | 0 | 2 | 0 | |||
| ext | 0 | 1 | 5 | 0 | 0 | 0 | 0 | 0 | - |
得到上表这个后，令ext[i]=e-i得5，这个时候，移动到下一个元素，但同时p暂时不动。这个情况出现于p<e的时候，严格来说，应该是z[i-p]+i < e的时候，具体原因后面解释。
| string | b | a | a | b | a | c | a | c | \0 |
|---|---|---|---|---|---|---|---|---|---|
| e | ^ | ||||||||
| i | ^ | ||||||||
| p | a | b | a | c | a | b | |||
| Z | 6 | 0 | 1 | 0 | 2 | 0 | |||
| ext | 0 | 1 | 5 | 0 | 0 | 0 | 0 | 0 | - |
上表这个时候，不看字符匹配的情况，只看i指针位置上那一列对应的Z数组的值，即z[i-p]为0，如果这个数加上i小于e的话，直接令ext[i]=z[i-p]得到0
| string | b | a | a | b | a | c | a | c | \0 |
|---|---|---|---|---|---|---|---|---|---|
| e | ^ | ||||||||
| i | ^ | ||||||||
| p | a | b | a | c | a | b | |||
| Z | 6 | 0 | 1 | 0 | 2 | 0 | |||
| ext | 0 | 1 | 5 | 0 | 1 | 0 | 0 | 0 | - |
继续以上操作，ext[i]=z[i-p]得到1。之所以能这么操作，是因为p是自匹配的，在这个位置上的z值，就同时表达了i开始，字符串s与p连续多少个字符能匹配p的前缀，前提是这个串的范围必须在e的前面。
| string | b | a | a | b | a | c | a | c | \0 |
|---|---|---|---|---|---|---|---|---|---|
| e | ^ | ||||||||
| i | ^ | ||||||||
| p | a | b | a | c | a | b | |||
| Z | 6 | 0 | 1 | 0 | 2 | 0 | |||
| ext | 0 | 1 | 5 | 0 | 1 | 0 | 0 | 0 | - |
继续以上操作，ext[i]=z[i-p]得到0，注意到，下一步i将指向a，导致z[i-p]+i >= e，这个会导致z数组的内容不能直接复制到ext数组内，所以我们要恢复之前的字符串匹配过程，令p等于i，得如下状态
| string | b | a | a | b | a | c | a | c | \0 |
|---|---|---|---|---|---|---|---|---|---|
| e | ^ | ||||||||
| i | ^ | ||||||||
| p | a | b | a | ||||||
| Z | 6 | 0 | 1 | ||||||
| ext | 0 | 1 | 5 | 0 | 1 | 0 | 1 | 0 | - |
这个时候，写入ext[i]=e-i得1
| string | b | a | a | b | a | c | a | c | \0 |
|---|---|---|---|---|---|---|---|---|---|
| e | ^ | ||||||||
| i | ^ | ||||||||
| p | a | b | |||||||
| Z | 6 | 0 | |||||||
| ext | 0 | 1 | 5 | 0 | 1 | 0 | 1 | 0 | - |
最后一步，第一个也不匹配，写入ext[i]=e-i得0，下一步i到达字符串末尾，结束。
扩展kmp与经典kmp的算法的时间复杂度均为 $O(len(s)+len(p))$
那么讲完了扩展KMP我们回来讲Z Algorithm，其实它们的区别，仅仅是计算对象的差异，即扩展KMP是通过字符串p求出s的ext数组，而Z Algorithm是通过自身来求，我们只需要把原来扩展KMP的代码复制一份改改名字，且起点改为1行了，详见下面模板实现代码。
应用实例有：hdu4333
KMP模板
以下是我写的模板代码
void kmp_next(const char* pattern, int next[])
{
int len = strlen(pattern);
next[0] = -1;
for (int i = 0, j = -1; i < len;)
{
if (j == -1 || pattern[i] == pattern[j])
next[++i] = ++j;
else
j = next[j];
}
}
const char* kmp_match(const char* str, const char* pattern, int next[])
{
int len = strlen(pattern);
int i = 0;
kmp_next(pattern, next);
while (*str && i < len)
{
if (pattern[i] == *str)
{
++i, ++str;
}
else
{
i = next[i];
if (i == -1)
{
++i, ++str;
}
}
}
return i == len ? str - i : str;
}
void extkmp_z(const char* str, int z[])
{
int s_len = strlen(str);
z[0] = s_len;
for (int i = 1, p = 1, e = 1; i < s_len; ++i)
{
if (i + z[i - p] >= e)
{
e = std::max(i, e);
p = i;
while (e < s_len && str[e] == str[e - i])
++e;
z[i] = e - i;
}
else
z[i] = z[i - p];
}
}
void extkmp_ext(const char* str, int ext[], const char* pattern, int z[])
{
int s_len = strlen(str);
extkmp_z(pattern, z);
for (int i = 0, p = 0, e = 0; i < s_len; ++i)
{
if (i + z[i - p] >= e)
{
e = std::max(i, e);
p = i;
while (e < s_len && str[e] == pattern[e - i])
++e;
ext[i] = e - i;
}
else
ext[i] = z[i - p];
}
}
最后总结
字符串就是一个深坑，不过KMP也许是打开你理解后缀树或后缀数组的好工具，为后者的学习做铺垫。
抱抱熊
一个喜欢折腾和研究算法的大学生