Boyer-Moore良好后缀启发式
我理解不良角色启发式的工作方式。 当您找到不匹配的字母x ，只需移动图案，使图案中最右侧的x与字符串中的x对齐。 并且它很容易在代码中实现。
我想我也理解良好后缀的启发式方法是如何工作的。 当我们找到一个好的后缀s ，在模式中的不同位置找到相同的后缀并移动它，使模式中的s与字符串中的s对齐。 但我不明白如何在代码中这样做。 我们如何找到模式中另一个地方是否存在相同的后缀？ 我们如何知道它的立场？ 代码：
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]=ji; j=f[j]; } i--; j--; f[i]=j; } }
来自http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm对我没有意义……有人可以为此任务编写尽可能简单的伪代码吗？ 或者以某种方式解释？
首先，我将使用p[i]表示模式中的字符，模式长度， $模式中的最后一个字符，即$ = p[m-1] 。
良好的后缀启发式案例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与下一场比赛（从右边开始计数）加上该比赛前的角色不同。
因此对于任何给定的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 ，这意味着从位置i开始的位置j开始的后缀的最宽边界。 我们想基于f[i]找到f[i-1] f[i] 。
例如，对于模式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 。 在位置， j-1=7 ，它是a = = p[4-1] ，即b 。 所以bcc不是边界。
我们知道bccaacc宽度> = 1的bccaacc必须以b加上从positin j = 8开始的后缀边界开始，在本例中为cc 。 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 ij - 1 jm pattern: abcdef ... @ x ... ? x ... $
如果位置i - 1字符@与字符相同? 在j - 1位置，我们知道f[i - 1] = j - 1; 或--i; --j; f[i] = j; --i; --j; f[i] = j; 。 边界是从位置j-1开始的后缀@x ... $ 。
但是如果位置i - 1字符@与字符不同? 在j - 1位置，我们必须继续向右搜索。 我们知道两个事实：（1）我们现在知道边界宽度必须小于从位置j开始的边界宽度，即小于x...$ 。 其次，边界必须以@...开头，以字符$结尾，否则可能为空。
基于这两个事实，我们继续在子字符串x ... $ （从位置j到m）内搜索以x开头的边界。 然后下一个边界应该是j ，等于f[j]; ，即j = f[j]; 。 然后我们将字符@与x之前的字符进行比较，即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] matches p [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] 。 但是当你为i = 1计算f[i-1] ，如果你没有测试if (s[j] == 0) ，你将再次设置s[7] 。 这意味着如果你在位置6处不匹配，你将3向右移动（将bdd对准cdd占用的位置）而不是6 （不移动直到add到cdd占用的位置）。
代码的评论
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]=ji; // 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; } }