KMP算法

算法简介

KMP算法解决的问题主要在于如何实现在一个较长的字符串中匹配得到一个较短的字符串。

我们知道对于子串匹配的问题，常用的暴力解法是不断枚举起点，并反复遍历字符串以确定是否匹配，而KMP算法则可以简化这一个过程。该算法可以自动跳过一些可能会导致重复匹配的字符串从而减少匹配的次数。

算法详解

首先我们假设我们待匹配的字符串是s = abababcafc而子串为p = ababc，整个匹配过程如下所示

abababcafc
ababc
    ^不匹配

abababcafc
  ababc
       ^匹配成功

我们可以发现与暴力匹配不同，字符串直接向后移动了两位然后完成了匹配，我们可以观察第二个字符串存在这样的性质

ab|ab|abcafc
^1 ^2
   ab|abc
   ^3

我们可以发现在这个串中1、2、3三个字符串均相同，实际上这里就是KMP移动字符串的依据，在第一次匹配的过程中我们发现字符串0-1位和2-3位相同，而第一次又成功匹配了0-3位的字符串，所以说实际上下一次进行匹配的时候我们的0-1位可以直接移动到当前2-3位的位置上，然后从2位重新开始匹配，从而减少了匹配的次数。

而此时我们便会面临一个问题，如何获得上面我们需要的这种相同的关系，此时我们可以考虑定义一个数组next[]，假设next[j]表示以j在p串中以j结尾的满足其前缀与后缀相同子串中前缀结尾的索引，而后续匹配时的跳转操作可以直接使用这个数组完成跳转。接下来我们可以尝试来计算这个数组。

next数组的计算方法

为了推导方便，此时我们假设p=ababdababaa，实际使用的时候我们只需要知道如何从next[0~i - 1]推得next[i]即可

//此时我们假设我们已知next[8]推导next[9]，我们有如下字符串，可以看到next[8] = 3
|aba|bd|aba|baa
//而正因为我们已知了next[8] = 3，我们知道p[1:3] == p[6:8]同时p[1:4] != p[5:8]，接下来我们继续向后读入一个字符
|aba|bd|aba|baa
     ^      ^p[9]
     p[next[9 - 1] + 1]
//可以发现此时p[next[9 - 1] + 1] == p[9]，故我们可以得到p[9] = p[8] + 1

但是我们面临着一个问题，如果第一次匹配不成功应该怎么解决，我们假设下面一种情况

|abab|d|abab|aa
 1234 5 6789 01
//此时我们需要计算next[10]，但是很不幸p[next[10 - 1] + 1] != p[10]

为了求解得到next[10]，我们只能退而求其次，去尝试更短的子串看看是否可以求解。根据next[9]=4我们可以知道p[1:4] == p[6:9]，而我们又可以发现next[next[9]] = next[4] = 2，即p[1:2] == p[3:4]，而根据next[9]的定义我们又知道p[3:4] == p[8:9]，同时p[next[next[9]] + 1] == p[10]，所以我们可以得到p[1:3] == p[8:10]即next[10] = 3。

而上面的推导存在一个边界，即当next[next[....]] = 0时，此时不再指望next[0~n-1]会对next[n]做出任何贡献。

next数组构造代码实现

for (int i = 2, j = 0; i <= m; ++i) // 假设字符串长度为m，且下标起点为1
{
	while(j && p[i] != p[j + 1]) j = next[j]; // 当出现退无可退（即j回到了0的位置）或匹配成功的时候跳出循环
  if (p[i] == p[j + 1]) j ++; // 对应了匹配成功的情况
  next[i] = j; 
}

匹配过程

既然此时我们获得了next[]，我们便可以开始尝试进行匹配s和p了，匹配过程与next[]构造的过程类似，即在出现第一个无法匹配即s[i] != p[j]或者匹配完全时，将会尝试最大程度的向前移动，这里我们还是继续假设待匹配的字符串是s = ababababfab而子串为p = ababf，匹配的过程可以像这样进行

ababababfab
ababf
    ^出现不匹配

此时我们要开始找最长的可以移动的距离，我们可以发现s[5] == p[3]，而同时存在p[1:2] == p[3:4]，故此时我们可以作如下的移动

ababababfab
  ababf
     ^下一个判断是否匹配的字符

可以看到这样我们就成功实现了利用next[]一次性移动多位的操作。这里的思想与求next[]的过程类似，即我们实际上是在s上搜索一个与当前已知前缀相互匹配的后缀，假设存在任何一个可以相互匹配的前后缀即可直接将字符串开头移动到求得的后缀的开头的位置。

匹配过程代码实现

for (int i = 1, j = 0; i <= n; ++i)
{
	while(j && s[i] != p[j + 1]) j = next[j]; // 在s上匹配一个p的后缀，而由于最终求得的前后缀是前面next数组得到的前后缀，故可以直接获得前文中三个子串相互的关系。
	if (s[i] == p[j + 1]) j ++; // 若当前位置匹配成功则后移待匹配的指针
	if (j == m) // j到达了p的末尾
	{
		// 匹配成功
		j = ne[j]; // 继续后移
	}
}

KMP算法的应用

状态机+KMP(AcWing 1052. 设计密码)

该题目中实际上可以将我们需要求得的密码视作n次状态转换，其中第一个状态即state[0]就是不存在任何匹配的状态，而由于我们的要求是不能匹配子串，假设子串长度为m，故我们要求不能到达state[m]。

由于密码的每一位都存在26种情况（题目中密码组成是全小写字母），故对于每一个状态均存在26种转移方式。而我们又知道对于KMP算法实际上每次在计算匹配情况的时候其都只会关心待匹配串s的一个字母，根据这种性质我们可以利用KMP的匹配方式求得每种状态最远可以匹配的子串长度，只要求得的长度没有到达n那就是一种可用的密码。

首先我们同样可以计算出KMP所需的next[]，然后可以进行状态转移

for (int i = 0; i < n; ++i)
{ 
	for (int j = 0; j < m; ++j) // 这里我们假设不能被包含的子串长度为m
	{
		for (char k = 'a'; k <= 'z'; ++k)
		{
			int u = j; // 这里的u即为我们当前k可以匹配到的最长子串长度，也就是说如果直接得到k == p[j + 1]时将会直接得到最大匹配长度
			while(u && k != p[u + 1]) u = next[u];
			if (k == p[u + 1]) u++;
			if (u < m) f[i + 1][u] = (f[i + 1][u] + f[i + 1][j]) % MOD;
		}
	}
}