我了解不良字符启发法的工作原理。当找到不匹配的字母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]=j-i;
j=f[j];
}
i--; j--;
f[i]=j;
}
}
从http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm中获取对我来说没有意义...有人可以为此任务编写尽可能简单的伪代码吗？或以某种方式解释？
最佳答案
首先，我将使用p[i]表示模式中的字符，m模式长度，$模式中的最后一个字符，即$ = p[m-1]。
良好的后缀启发式案例1有两种情况。
情况1
考虑以下示例，
leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch here
因此，模式
XXX中的子字符串cXXXbXXXcXXXcXXX是很好的后缀。不匹配发生在字符c。那么在不匹配之后，我们应该将4移到右边还是8？如果我们按如下所示将4移位，则将再次发生相同的错误（
b导致错误c）， leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch occurs here again
因此，在这种情况下，我们实际上可以向右移动8个字符。
情况二
让我们来看另一个例子
leading TEXT cXXXcXXXbXXXcXXX rest of the TEXT
cXXXXcXXXbXXXcXXX
^
| mismatch happens here
我们可以在这里移动4或8或更多吗？显然，如果我们移位8或更多，我们将错过将模式与文本匹配的机会。因此，在这种情况下，我们只能向右移动4个字符。
那么这两种情况有什么区别？
区别在于，在第一种情况下，不匹配的字符
c加上后缀XXX为cXXX，与下一个（从右数起）匹配的XXX加上前一个字符相同那。在第二种情况下，cXXX与下一个匹配项（从右数起）加上该匹配项之前的字符不同。因此，对于任何给定的GOF SUFFIX（让我们将其称为
XXX），我们需要弄清楚这两种情况下的变化，（1）在GOOD SUFFIX和GOOD SUFFIX之前的字符（我们将其称为c），模式中的字符也匹配好后缀+下一个字符的下一个（从右数）匹配，（2）字符加GOF 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]的字母，这意味着从位置i < k < m开始于位置i的后缀的最宽边框。我们想基于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边界必须以
bccaacc开头，后缀的边界必须从positin b开始，在本例中为j = 8。 cc在cc位置上的c边框最宽。因此，我们继续比较j = f[8]与9。他们又不平等了。现在后缀为p[4-1]，并且在位置p[j-1]处只有零长度的边框。所以现在是p[9] = c，它是10。因此，我们继续进行比较，将j = f[9]与10进行比较，它们不相等，那就是字符串的结尾。那么p[4-1]仅具有零长度的边框，使其等于10。从更一般的意义上描述过程
因此，
p[j-1]的含义是这样的， Position: 012345 i-1 i j - 1 j m
pattern: abcdef ... @ x ... ? x ... $
如果位置
f[3]处的字符f[i] = j与位置@处的字符i - 1相同，我们知道?或j - 1。边框后缀f[i - 1] = j - 1;从位置--i; --j; f[i] = j;开始。但是，如果位置
@x ... $上的字符j-1与位置@上的字符i - 1不同，我们必须继续在右侧搜索。我们知道两个事实：（1）现在我们知道边界宽度必须小于从位置
?开始的宽度，即小于j - 1。其次，边框必须以j开头并以字符x...$结束，否则可以为空。基于这两个事实，我们继续在子字符串
@...（从位置j到m）中搜索以$开头的边框。然后，下一个边框应位于等于x ... $的x，即j。然后，我们将字符f[j];与j = f[j];之前的字符（在@处）进行比较。如果它们相等，则找到边界，否则，继续进行处理，直到j> m。以下代码显示了此过程， while (j<=m && p[i-1]!=p[j-1])
{
j=f[j];
}
i--; j--;
f[i]=j;
现在查看条件
x p [j-1] j-1 p [i] p[i -1] != p [j] , this is what we talked about in situation (2), p [i -1]！= matches，因此我们从, but转换为p[j-1]，即i。现在剩下的唯一没有解释的是测试
j，当较短的后缀具有相同的边框时，将发生该测试。例如，您有一个模式 012345678
addbddcdd
计算
s[j] = j - i;和if (s[j] == 0)时，将设置f[i - 1]。但是，当您为i = 4计算s[7]时，如果没有测试f[i-1]，则将再次设置i = 1。这意味着，如果在位置s[7]不匹配，则将if (s[j] == 0)向右移动（将6与所占据的位置3对齐）而不是bdd（直到cdd移至位置6占据）。代码注释
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;
}
}
关于c - Boyer-Moore良好后缀的启发式方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19345263/