构建一个好的后缀表 - 理解示例

Question

我真的很想了解一个关于如何为给定模式构建好的后缀表的示例。问题是，我无法理解它。我看过很多例子，但不知道这些数字来自哪里。

所以这里是： 以下示例演示了如何根据模式 ANPANMAN 构建Good Suffix Table：

Index | Mismatch | Shift | goodCharShift
-----------------------------------------------
  0   |         N|   1   | goodCharShift[0]==1
  1   |        AN|   8   | goodCharShift[1]==8
  2   |       MAN|   3   | goodCharShift[2]==3
  3   |      NMAN|   6   | goodCharShift[3]==6
  4   |     ANMAN|   6   | goodCharShift[4]==6
  5   |    PANMAN|   6   | goodCharShift[5]==6
  0   |   NPANMAN|   6   | goodCharShift[6]==6
  0   |  ANPANMAN|   6   | goodCharShift[7]==6

非常感谢有关此事的任何帮助。我根本不知道如何获得这些数字。谢谢！

Answer 1

第 1 行，没有匹配的字符，读取的字符不是 N。良好后缀长度为零。由于模式中有很多字母也不是 N，因此我们这里的信息很少 - 移动 1 是最不有趣的结果。

第2行我们匹配了N，它前面有A以外的东西。现在看看从末尾开始的模式，N前面哪里有A以外的东西？还有另外两个 N，但两者前面都有 A。这意味着好后缀的任何部分对我们来说都没有用处——移动完整模式长度 8。

第3行：我们匹配了AN，它前面不是M。在模式中间有一个AN，前面有P，所以它成为移位候选者。将该 AN 向右移动以与我们的匹配对齐，即移动 3。

第 4 行及以上：匹配的后缀与模式中的其他任何内容都不匹配，但尾随后缀 AN 与模式的开头匹配，因此此处的移位均为 6。

Answer 2

它可能会帮助你好的后缀表。

为什么你没有尝试使用最后出现的方法，与好的后缀表相比，它要容易得多。我使用最后出现的方法进行搜索

Answer 3

虽然这是一个老问题，并且有一个答案被接受，但我只想添加 JHU 的 pdf，它很好地解释了良好的后缀规则。 http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf

这个 pdf 让我的生活变得更加轻松。所以希望它也能帮助那些努力理解这个算法的人。