首先，我将使用p[i]表示模式中的一个字符，m模式长度，模式中$的最后一个字符，即$ = p[m-1].
好的后缀启发式案例 1 有两种情况。
情况一
考虑以下示例，
leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch here
XXX所以模式中的子字符串cXXXbXXXcXXXcXXX是好的后缀。不匹配发生在 character 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，与下一个（从右数）匹配的 forXXX加上之前的字符相同。而在第二种情况下，cXXX不等于下一个匹配项（从右数）加上该匹配项之前的字符。
所以对于任何给定的 GOOD SUFFIX（我们称之为XXX），我们需要弄清楚这两种情况下的移位，（1）在 GOOD SUFFIX 加上 GOOD SUFFIX 之前的字符（我们称之为c），在模式中也是匹配的好的后缀+之前的字符的下一个（从右数）匹配，（2）字符加上GOOD SUFFIX不匹配
对于情况（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;在代码中。
边界
要考虑所有好的后缀，我们首先需要了解什么是所谓的border. 边框是一个子字符串，它既是字符串的proper前缀又proper是字符串的后缀。例如，对于一个字符串XXXcXXX，X是一个边框，XX也是一个边框XXX。但XXXc不是。我们需要确定模式后缀最宽边框的起点，并将此信息保存在数组中f[i]。
如何确定f[i]？
假设我们知道f[i] = j并且对于所有其他f[k]s i < k < m，这意味着从 position 开始的后缀的最宽边框i开始于 position j。我们要f[i-1]根据f[i].
例如，对于模式aabbccaacc，在位置i=4，后缀是ccaacc，其最宽的边框是cc( p[8]p[9])，所以j = f[i=4] = 8。现在我们想f[i-1] = f[3]根据我们所拥有的信息来了解f[4], f[5], ... 因为f[3], 现在的后缀是bccaacc. 在位置 ,j-1=7是a!=p[4-1]是b. 所以bcc不是边界。
我们知道任何宽度 >= 1 of的边框bccaacc都必须以b加上从 positin 开始的后缀的边框开始，在这个例子j = 8中就是这样。在 位置有最宽的边界。所以我们继续我们的搜索与比较。他们又不相等了。现在后缀是并且它在位置只有零长度边界。所以现在它是。所以我们通过比较来继续搜索，它们不相等，这是字符串的结尾。然后只有零长度边界，使其等于 10。cccccj = f[8]9p[4-1]p[j-1]p[9] = c10j = f[9]10p[4-1]p[j-1]f[3]
在更一般的意义上描述这个过程
因此，f[i] = j意思是这样的，
Position: 012345 i-1 i j - 1 j m
pattern: abcdef ... @ x ... ? x ... $
如果 position 处的字符@与 position处i - 1的字符相同，我们知道
, 或。边框是从 position 开始的后缀。?j - 1f[i - 1] = j - 1; --i; --j; f[i] = j;@x ... $j-1
但是如果@position处的字符与 positioni - 1处的字符不同，我们必须继续向右搜索。我们知道两个事实：（1）我们现在知道边框宽度必须小于从 position 开始的宽度，即小于。其次，边框必须以字符开头和结尾，否则可能为空。?j - 1jx...$@...$
基于这两个事实，我们继续在子字符串x ... $（从位置 j 到 m）中搜索以 开头的边框x。那么下一个边界应该j是等于 f[j];，即j = f[j];。然后我们将字符@与之前的字符进行比较x，即 at j-1。如果相等，我们就找到了边界，如果不相等，继续这个过程直到 j > m。此过程由以下代码显示，
while (j<=m && p[i-1]!=p[j-1])
{
j=f[j];
}
i--; j--;
f[i]=j;
现在看看条件p[i -1] != p[j-1] , this is what we talked about in situation (2), p[i] matchesp[j] , but 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，你会重新设置。这意味着如果您在 position 处不匹配，则向右移动（与占用的位置对齐）而不是（直到移动到占用的位置）。s[7]if (s[j] == 0)63bddcdd6addcdd
代码注释
void bmPreprocess1()
{
// initial condition, set f[m] = m+1;
int i=m, j=m+1;
f[i]=j;
// calculate f[i], s[j] from i = m to 0.
while (i>0)
{
// at this line, we know f[i], f[i+1], ... f[m].
while (j<=m && p[i-1]!=p[j-1]) // calculate the value of f[i-1] and save it to j-1
{
if (s[j]==0) s[j]=j-i; // if s[j] is not occupied, set it.
j=f[j]; // get the start position of the border of suffix p[j] ... p[m-1]
}
// assign j-1 to f[i-1]
i--; j--;
f[i]=j;
}
}