首先，我将使用p[i]表示模式中的一个字符，m表示模式长度，$表示模式中的最后一个字符，即$ = p[m-1]。
好后缀启发式算法有两种情况，第一种情况如下：
情况1
考虑以下例子：
leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch here
因此，在模式 cXXXbXXXcXXXcXXX 中，子字符串 XXX 是好的后缀。不匹配发生在字符 c 上。那么在不匹配后，我们应该向右移动4还是8个位置？
如果像下面一样向右移动4个位置，则会再次出现相同的不匹配（ b 与 c 不匹配），
leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch occurs here again
因此，在这种情况下，我们实际上可以将8个字符向右移动。
情况2
让我们看另一个例子。
leading TEXT cXXXcXXXbXXXcXXX rest of the TEXT
cXXXXcXXXbXXXcXXX
^
| mismatch happens here
我们可以将其向右移动4或8个字符吗？显然，如果我们移动8个或更多的字符，我们将错过使用文本匹配模式的机会。因此，在这种情况下，我们只能将4个字符向右移动。
那么这两种情况有什么区别呢？
区别在于，在第一种情况下，不匹配的字符 c 加上良好后缀XXX，即 cXXX ，与下一个（从右数）匹配XXX的相同，加上前一个字符。而在第二种情况下， cXXX 与下一个匹配（从右数），加上该匹配项之前的字符不同。
因此，对于任何给定的良好后缀（让我们称其为XXX），我们需要确定这两种情况的移位，（1）在模式中，良好后缀之前的字符（让我们称其为c）加上良好后缀，也与良好后缀的下一个（从右数）匹配加上它之前的字符，（2）字符加上良好后缀不匹配。
例如，对于情况（1），如果您有一个模式0XXXcXXXcXXXcXXXcXXXcXXX，如果第一个 c 的测试失败后，您可以将20个字符向右移动，并将0XXX与已经测试过的文本对齐。
这就是计算数字20的方式，
1 2
012345678901234567890123
0XXXcXXXcXXXcXXXcXXXcXXX
^ ^
在不匹配的位置是20，移位的子字符串
0XXX将从20到23占据位置。而
0XXX以位置0开始，所以20-0=20。
对于情况（2），例如在这个例子中，
0XXXaXXXbXXXcXXX，如果在第一次测试
c失败后，您只能向右移动4个字符，并将
bXXX与已测试的文本对齐。
这就是数字
4的计算方式。
0123456789012345
0XXXaXXXbXXXcXXX
不匹配发生的位置是12，下一个字符串是bXXX，以8为起始位置，12-8=4。如果我们设定j=12，i=8，那么移位就是j-i，也就是在代码中的s[j] = j - i;。
边界
为了考虑所有好的后缀，我们首先需要了解什么是所谓的边界。边界是既是一个合适的前缀又是一个合适的后缀的子字符串。例如，在字符串XXXcXXX中，X是一个边界，XX是一个边界，XXX也是一个边界。但是XXXc不是。我们需要确定模式后缀的最宽边界的起始点，并将这个信息保存在数组f[i]中。
如何确定f[i]？
假设我们知道f[i]=j，并且对于所有其他f[k]（其中i < k < m），即从位置i开始的后缀的最宽边界始于位置j。我们想要根据f[i]找到f[i-1]。
例如，对于模式aabbccaacc，在位置i=4处，后缀是ccaacc，最宽的边界是cc（p[8]p[9]），所以j=f[i=4]=8。现在我们想根据我们拥有的关于f[4]、f[5]等的信息来了解f[i-1]=f[3]。对于f[3]，后缀现在是bccaacc。在位置处，它是a!=p[4-1]，即b。因此，bcc不是一个边界。
我们知道，宽度 >= 1 的边界bccaacc必须以 b 开头，并从位置j = 8开始搜索后缀的边界，这个例子中是cc。在位置j = f[8]处有最宽的边界c，即9。因此，我们继续比较p[4-1]和p[j-1]。它们再次不相等。现在后缀是p[9] = c，并且在位置10处只有零长度的边界。所以现在j = f[9]，而它是10。所以我们继续比较p[4-1]和p[j-1]，它们不相等，那就是字符串的结尾了。然后，f[3]只有零长度边界，使其等于10。
更一般地描述该过程
因此，f[i] = j的意思是这样的,
Position: 012345 i-1 i j - 1 j m
pattern: abcdef ... @ x ... ? x ... $
如果在位置i-1处的字符@与位置j-1处的字符?相同，那么我们知道
f[i - 1] = j - 1; 或 --i; --j; f[i] = j;。边界是从位置j-1开始的后缀 @x ... $。
但是，如果在位置i-1处的字符@与位置j-1处的字符?不同，
我们必须继续向右搜索。 我们知道两个事实：（1）现在我们知道边界宽度必须小于从位置开始的宽度，即小于x...$。其次，边界必须以@...开头并以字符$结尾，或者可能为空。
基于这两个事实，我们在子字符串x ... $（从位置j到m）内继续搜索以x开头的边界。然后下一个边界应该在j处，即等于f[j]，即j=f[j]。然后我们将字符@与x之前的字符（位于j-1处）进行比较。如果它们相同，我们就找到了边界，否则继续这个过程直到m。 这个过程由下面的代码展示：
while (j<=m && p[i-1]!=p[j-1])
{
j=f[j];
}
i
f[i]=j;
现在看一下条件p[i-1] != p[j-1]，这就是我们在情况（2）中讨论过的，即p[i]与p[j]匹配，但p[i-1] != p[j-1]，所以我们从i移动到j，即s[j] = j - i;。
现在唯一没有解释的是测试if(s[j] == 0)，当一个更短的后缀具有相同的边界时，它将发生。例如，你有一个模式
012345678
addbddcdd
当你计算
f[i - 1]并且
i = 4时，你会设置
s[7]。但是当你计算
f[i-1]并且
i = 1时，如果没有测试
if (s[j] == 0)，你会再次设置
s[7]。这意味着如果你在位置
6上有不匹配，你需要将
3向右移（使
bdd与占据位置的
cdd对齐），而不是将其移动到
6（不要将其移动直到
add到占据位置的
cdd）。
void bmPreprocess1()
{
int i=m, j=m+1;
f[i]=j;
while (i>0)
{
while (j<=m && p[i-1]!=p[j-1])
{
if (s[j]==0) s[j]=j-i;
j=f[j];
}
i--; j--;
f[i]=j;
}
}
